Xin cảm ơn DevGang đã cung cấp bộ đề, test và lời giải cho bài này.

An và Bình chơi với nhau rất thân. Hai bạn thường chơi đố vui trong những giờ rảnh rỗi. Một lần, An cho Bình một bài toán như sau:

Cho một dãy số nguyên $A$ gồm $n$ phần tử được đánh số từ ~1~ đến $n$. Ban đầu tất cả các phần tử của dãy đều có giá trị là ~0~. Thực hiện $Q$ lần thay đổi giá trị các phần tử của dãy. Lần thứ $i$ trong $Q$ lần đó, thực hiện thay đổi từ phần tử thứ $u$ đến phần tử thứ $v$ một lượng là $M$, nghĩa là nếu $M$ âm thì mỗi phần tử trong đoạn $[u,v]$ sẽ giảm đi $M$, còn $M$ dương thì tăng mỗi phần tử đó lên $M$. Sau $Q$ lần thực hiện thay đổi như thế, hãy cho biết số lớn nhất trong dãy là bao nhiêu?

Em hãy giúp Bình tìm ra đáp án của bài toán nhé!

Dữ liệu vào

Đọc từ file văn bản FINDMAX.INP gồm:

• Dòng thứ nhất chứa hai số nguyên $n$ và $Q$, giữa hai số cách nhau một khoảng trắng ($1\le n,Q\le {10}^6$).

• Dòng thứ hai đến dòng $Q+1$, mỗi dòng gồm ba số nguyên $u,v,M$, giữa hai số cách nhau một khoảng trắng ($1\le u\le v\le n$ và $M\ne 0$, $|M|\le {10}^6$).

Kết quả ra

Ghi ra văn bản FINDMAX.OUT số lớn nhất tìm được.

Ràng buộc

• Có ~70\%~ test có $1\le n,Q\le {10}^3$.

• Có ~30\%~ test có ${10}^3<n$, $Q\le {10}^6.$

Ví dụ

Dữ liệu

4 3
1 2 3
2 4 -1
3 4 7

Kết quả

6

Giải thích

Với $n=4$, $Q=3$ dãy ban đầu: 0 0 0 0 Có ~3~ lần biến đổi:

• Sau lần biến đổi thứ nhất dãy trở thành: 3 3 0 0

• Sau lần biến đổi thứ hai dãy trở thành: 3 2 -1 -1

• Sau lần biến đổi thứ ba dãy trở thành: 3 2 6 6

Kết quả: Giá trị lớn nhất của dãy là 6.