問題文

無限に長い数直線上に，$N$ 個の湖と $M$ 匹の魚がいます．

$i$ 番目の湖の範囲は，$[L_i - 0.5, L_i + 0.5)$ で表されます．また，$i$ 番目の魚は，最初座標 $F_i$ に位置しています．

ある魚が座標 $x$ にいるとき，ある湖が存在して，座標 $x$ がその湖の範囲に含まれる場合，その魚は水中にいると言い，そうでない場合，その魚は地上にいると言います．

魚には強さが定められており，$i$ 番目の魚について，地上にいる場合の強さは $B_i$，水中にいる場合の強さは $W_i$ です．すべての $i$ について，$B_i \leq W_i$ が成り立つことが保証されます．

あなたは，次の操作を何回でも行うことができます．

• 魚を一匹選び，その魚を数直線の正の向きに $1$ だけ動かす．この操作には，コストが $1$ かかる．
• 魚を一匹選び，その魚を数直線の負の向きに $1$ だけ動かす．この操作には，コストが $1$ かかる．

操作後における $M$ 匹の魚の強さの合計値を $S$，操作によってかかったコストの合計値を $C$ としたとき，$S-C$ の最大値を求めてください．

制約

• 入力はすべて整数である．
• $1 \leq N, M \leq 10^5$
• $0 \leq L_1 < L_2 < \dots < L_N \leq 10^9$
• $0 \leq F_i \leq 10^9$
• $0 \leq B_i \leq W_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$
$L_1$ $L_2$ $\cdots$ $L_N$
$F_1$ $B_1$ $W_1$
$F_2$ $B_2$ $W_2$
$\vdots$
$F_M$ $B_M$ $W_M$

出力

答えを出力せよ．

サンプル

4 3
8 11 14 2023
7 10 12
14 14 14
2013 8 12

33

1 1
0
0 0 1000000000

1000000000

6 5
57 59 60 72 85 91
12 3 55
16 58 96
94 77 85
97 20 77
37 7 53

254