#AT23. Intervals

Intervals

[W] Intervals(dp_w)

来源: AtCoder Educational DP Contest - Problem W 原题时限:2 秒 / 内存:1024 MB

题目描述

考虑一个长度为 NN 的、仅由 0 与 1 构成的字符串。字符串的分数按下式计算:

  • 对于每个 ii(1≤i≤M1 \le i \le M),若字符串在第 lil_i 个到第 rir_i 个字符(含两端)之间至少出现一次 1,则分数加上 aia_i。

求字符串可能得到的最大分数。

输入格式

输入由标准输入按以下格式给出:

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

输出格式

输出字符串可能得到的最大分数。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤M≤2×1051 \le M \le 2 \times 10^5
  • 1≤li≤ri≤N1 \le l_i \le r_i \le N
  • ∣ai∣≤109|a_i| \le 10^9

样例 1

输入:

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

输出:

20

样例 2

输入:

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

输出:

90

样例 3

输入:

1 1
1 1 -10

输出:

0

样例 4

输入:

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

输出:

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

输出:

10