001 - Imos

時間制限 2 秒 / メモリ制限 64 MB / 得点 10 / x 0 /


TLE
2sec
MLE
64MB
得点
10

問題

山本君は山田君から長さ $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$

入出力例

例1

入力

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

例2

入力

10 0

出力

0