Intervals

题意翻译

给定 $m$ 条规则形如 $(l_i,r_i,a_i)$，对于一个 01 串，其分数的定义是：对于第 $i$ 条规则，若该串在 $[l_i,r_i]$ 中至少有一个 1，则该串的分数增加 $a_i$。 你需要求出长度为 $n$ 的 01 串中的最大分数。 $1\le n,m\le 2\times 10^5$，$|a_i|\le 10^9$。

题目描述

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_w 長さ $ 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 $ となります。