← 返回题目列表

AtCoder · dp_w

W. 间隔

中文机器翻译题面 查看原题

分数: 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.