W - Intervals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ 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

出力

文字列のスコアの最大値を出力せよ。

入力例 1

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

出力例 1

20

10001 のスコアは 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 のスコアは a_1 + a_2 = 100 + (-10) = 90 となります。

入力例 3

1 1
1 1 -10

出力例 3

0

0 のスコアは 0 となります。

入力例 4

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

出力例 4

5000000000

答えは 32-bit 整数型に収まらない場合があります。

入力例 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 のスコアは a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10 となります。

Score : 100 points

Problem Statement

Consider a string of length N consisting of 0 and 1. The score for the string is calculated as follows:

  • For each i (1 \leq i \leq M), a_i is added to the score if the string contains 1 at least once between the l_i-th and r_i-th characters (inclusive).

Find the maximum possible score of a string.

Constraints

  • All values in input are integers.
  • 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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of a string.

Sample Input 1

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

Sample Output 1

20

The score for 10001 is a_1 + a_3 = 10 + 10 = 20.

Sample Input 2

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

Sample Output 2

90

The score for 100 is a_1 + a_2 = 100 + (-10) = 90.

Sample Input 3

1 1
1 1 -10

Sample Output 3

0

The score for 0 is 0.

Sample Input 4

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

Sample Output 4

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 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

Sample Output 5

10

For example, the score for 101000 is a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10.