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