问题陈述

考虑一个长度为 $N$ 的字符串，它由 0 和 1 组成。该字符串的得分计算如下：

• 对于每个 $i$ ( $1 \leq i \leq M$ )，如果字符串在第 $l_i$ 和第 $r_i$ 个字符(包括在内)之间至少包含一次 1 ，则得分将增加 $a_i$ 。

找出字符串的最大可能得分。

限制因素

• 所有输入值均为整数。
• $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$

输入

输入内容由标准输入法提供，格式如下：

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

输出

打印字符串的最大可能得分。

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

20

10001 的得分是 $a_1 + a_3 = 10 + 10 = 20$ 。

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

90

100 的得分是 $a_1 + a_2 = 100 + (-10) = 90$ 。

1 1
1 1 -10

0

0 的得分是 $0$ 。

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

5000000000

答案可能不适合 32 位整数类型。

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

例如，101000 的得分是 $a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10$ 。

来源

https://atcoder.jp/contests/dp/tasks/dp_w