题目描述

長さ $N$ の 0 と 1 からなる文字列を考えます。 この文字列のスコアを次のように計算します。

• 各 $i$ ($1\ \leq\ i\ \leq\ M$) について、$l_i$ 文字目から $r_i$ 文字目までに 1 がひとつ以上含まれるならば、スコアに $a_i$ を加算する。

文字列のスコアの最大値を求めてください。

输入格式

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

$N$ $M$ $l_1$ $r_1$ $a_1$ $l_2$ $r_2$ $a_2$ $:$ $l_M$ $r_M$ $a_M$

输出格式

文字列のスコアの最大値を出力せよ。

题目大意

给定 $m$ 条规则形如 $(l_i,r_i,a_i)$，对于一个 01 串，其分数的定义是：对于第 $i$ 条规则，若该串在 $[l_i,r_i]$ 中至少有一个 1，则该串的分数增加 $a_i$。

你需要求出长度为 $n$ 的 01 串中的最大分数。

$1\le n,m\le 2\times 10^5$，$|a_i|\le 10^9$。

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

20

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

90

1 1
1 1 -10

0

1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

5000000000

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

10

提示

制約

• 入力はすべて整数である。
• $1\ \leq\ N\ \leq\ 2\ ×\ 10^5$
• $1\ \leq\ M\ \leq\ 2\ ×\ 10^5$
• $1\ \leq\ l_i\ \leq\ r_i\ \leq\ N$
• $|a_i|\ \leq\ 10^9$

Sample Explanation 1

10001 のスコアは $a_1\ +\ a_3\ =\ 10\ +\ 10\ =\ 20$ となります。

Sample Explanation 2

100 のスコアは $a_1\ +\ a_2\ =\ 100\ +\ (-10)\ =\ 90$ となります。

Sample Explanation 3

0 のスコアは $0$ となります。

Sample Explanation 4

答えは 32-bit 整数型に収まらない場合があります。

Sample Explanation 5

例えば、101000 のスコアは $ a_2\ +\ a_3\ +\ a_4\ +\ a_5\ +\ a_7\ =\ 10\ +\ (-8)\ +\ 5\ +\ 9\ +\ (-6)\ =\ 10 $ となります。