Atcoder Educational DP Contest W - Intervals

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
hiepnnguyen
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Xét một xâu có chiều dài ~N~ bao gồm các chữ số 0 và 1. Điểm của xâu được tính như sau:

  • Với mỗi số nguyên ~i~ (~1~ ≤ ~i~ ≤ ~M~), tổng số điểm của xâu được tăng thêm ~a_i~ nếu như xâu con bao gồm các kí tự từ ~l_i~ đến ~r_i~ (kể cả biên) có ít nhất một kí tự 1.

Với mọi xâu độ dài ~N~, số điểm cao nhất có thể đạt được là bao nhiêu?

Input

  • Dòng đầu chứa hai số nguyên ~N, M~ (~1 \le N \le 2 \cdot 10^5~ và ~1 \le M \le 2 \cdot 10^5~).
  • ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~l_i, r_i, a_i~ (~1 \le l_i \le r_i \le N~ và ~\mid a_i\mid \le 10^9~).

Output

Số điểm tối đa mà xâu có thể đạt được.

Sample 1

Input
5 3
1 3 10
2 4 -10
3 5 10
Output
20
Giải thích

Điểm cho xâu 10001 là ~a_1 + a_3 = 10 + 10 = 20~.

Sample 2

Input
3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30
Output
90
Giải thích

Điểm cho xâu 100 là ~a_1 + a_2 = 100 + (-10) = 90~.

Sample 3

Input
1 1
1 1 -10
Output
0
Giải thích

Điểm cho xâu 0 là ~0~.

Sample 4

Input
1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
Output
5000000000

Kết quả có thể không phù hợp với số nguyên có định dạng 32-bit.

Sample 5

Input
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
Output
10
Giải thích

Điểm cho xâu 101000 là ~a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10~.

Comments

Please read the guidelines before commenting.