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é!

Input

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 ≠ 0, |M| ≤ 10^6)~.

Output

In ra số lớn nhất tìm được.

Sample Input

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

Sample Output

6

Subtask

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

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

Giải thích

Với ~n = 4, Q = 3~, dãy ban đầu: ~0 0 0 0~

Sau lần biến đổi thứ nhất: ~3 3 0 0~

Sau lần biến đổi thứ hai: ~3~ ~2~ ~-1~ ~-1~

Sau lần biến đổi thứ ba: ~3~ ~2~ ~6~ ~6~

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