由于输了比赛，小 $C$ 需要请客。但是现在外面已经是大雪连天了，所以小C决定叫外卖。

受到雪灾的影响，很多餐厅没有采购到足够的食材，因此小C不得不从不同的餐厅购买食物，更加悲催的是因为雪灾的原因，送餐员最多只能携带一道菜，且最多只送一次。

现在小 $C$ 需要叫 $n$ 道菜，于是他联系了 $n$ 名送餐员。

送餐员和餐厅可以看成在一条直线上。第 $i$ 名送餐员有一个整数坐标 $x_i$，且他索要的工资为$|\text{他所在的坐标}-\text{餐厅的坐标}|$元。 第 $j$ 家餐厅有一个整数坐标 $y_j$，且它们的食材只能提供不超过 $c_j$ 道菜，每道菜价值 $w_j$ 元。

现在小 $C$ 希望知道，他的最小花费。

输入格式

第一行两个整数 $n,m$，表示送餐员的数量和餐厅的数量。

接下来一行 $n$ 个整数表示 $x_1 \ldots x_n$，保证 $ x_i \le x_{i + 1} $ 。

接下来 $m$ 行，第 $i$ 行包括三个整数 $y_i,w_i,c_i$，保证 $ y_i \le y_{i + 1} $ 。

输出格式

输出一个整数表示答案，无解输出 -1.

4 4
8 8 9 10
1 4 1
3 0 1
5 0 1
10 2 1

22

小 $ C $ 的最优方案为：第一个送餐员去第一个餐厅，第二个送餐员去第二个餐厅，第三个送餐员去第三个餐厅，第四个送餐员去第四个餐厅。这种方案的总花费为 $ 22 $。

样例二至样例七

见样例数据下载

限制与约定

对于100%的数据，有 $2 \le n,m \le 10^5, 0 \le x_i, y_i, c_i, w_i \le 10^9$。

Subtask 1(5 分): $n,m \le 5​$

Subtask 2(20 分): $n \le 300,m \le 1000$

Subtask 3(25 分): $n,m \le 5000$

Subtask 4(9 分): $\forall i \in [1,m],w_i=0,\sum_{i=1}^{m}c_i \le 10^6$

Subtask 5(11 分): $\sum_{i=1}^{m}c_i \le 10^6$

Subtask 6(11 分): $\forall i \in [1,m],w_i=0$

Subtask 7(19 分): 无其他限制

时间限制：$\texttt{1s}$

空间限制：$\texttt{256MB}$

下载

样例数据下载