001 - Imos

問題

山本君は山田君から長さ $N$ の配列$A=(a_1,a_2,...,a_N)$をもらった。
しかし、配列の初期値はすべて0となっており面白みがないので以下のように $Q$ 回の加算を行うことにした。

• 整数 $l,r,v$ が $Q$ 回与えられるので$ \ A_l,A_{l+1},\ldots,A_r \ $に$v$を加算する。

$Q$ 回の加算を終えた後、配列 $A$ の各要素の中で最も大きい値を出力せよ。

入力

$N$ $Q$
$l_1$ $r_1$ $v_1$
$l_2$ $r_2$ $v_2$
$...$
$l_Q$ $r_Q$ $v_Q$

出力

$Q$ 回の加算を終えた後、配列 $A$ の各要素の中で最も大きい値を出力する。
出力の末尾には改行を入れること。

制約

• $1 \leq N \leq 10^{18}$
• $0 \leq Q \leq 10^5$
• $1 \leq l_i \leq r_i \leq N$
• $-10^9 \leq v_i \leq 10^9$
• $1 \leq i \leq Q$

入出力例

例１

入力

5 4
1 5 2
1 3 3
5 5 -10
3 5 5

出力

10

解説

• 1回目: 2 2 2 2 2
• 2回目: 5 5 5 2 2
• 3回目: 5 5 5 2 -8
• 4回目: 5 5 10 7 -3

例２

入力

10 0

出力

0