分数: 100 点
问题陈述
考虑一个长度的字符串 N 组成 0 和 1。
字符串的分数计算如下:
如果字符串包含
- 对于每个 i (1 \leq i \leq M), a_i 将添加到分数
1之间至少一次 l_i-th 和 r_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
输出
打印字符串的最大可能分数。
示例输入 1
5 3 1 3 10 2 4 -10 3 5 10
示例输出 1
20
的分数 10001 is a_1 + a_3 = 10 + 10 = 20.
示例输入 2
3 4 1 3 100 1 1 -10 2 2 -20 3 3 -30
示例输出 2
90
的分数 100 is a_1 + a_2 = 100 + (-10) = 90.
示例输入 3
1 1 1 1 -10
示例输出 3
0
的分数 0 is 0.
示例输入 4
1 5 1 1 1000000000 1 1 1000000000 1 1 1000000000 1 1 1000000000 1 1 1000000000
示例输出 4
5000000000
答案可能不适合 32 位整数类型。
示例输入 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
例如,分数 101000 is a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10.