区间激活最大得分(Intervals)

题目描述

長さ $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$

输出格式

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

样例输入 #1

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

样例输出 #1

20

样例输入 #2

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

样例输出 #2

90

样例输入 #3

1 1
1 1 -10

样例输出 #3

0

样例输入 #4

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

样例输出 #4

5000000000

样例输入 #5

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

样例输出 #5

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$ となります。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接