QUEMAX
Cho một dãy số \(a_1, a_2, ..., a_n\), ban đầu \(a_i = 0\), với mọi i = 1,2…, n và \(m\) truy vấn dạng \(Q(u, v, k)\) tương ứng tăng các giá trị \(a[u], a[u+1], …, a[v]\) lên một lượng bằng \(k\).
Yêu cầu: Sau \(m\) truy vẫn, hãy tìm giá trị lớn nhất của dãy trên.
Dữ liệu vào:
Dòng đầu ghi hai số nguyên dương \(n, m (1 ≤ n ≤ 10^7, 1 ≤ m ≤ 2.10^5)\)
\(m\) Dòng tiếp theo, dòng thứ ghi truy vấn gồm ba số nguyên không âm \(u, v, k (1 ≤ u ≤ v ≤ n, 1 ≤ k ≤ 10^9)\)
Dữ liệu ra:
- Ghi ra một số nguyên duy nhất là giá trị lớn nhất của dãy sau \(m\) truy vấn.
Sample Input
5 3
1 2 100
2 5 100
3 4 100
Sample Output
200
Comments