Cho dãy số nguyên ~X_1, X_2, \dots, X_n~ ban đầu có giá trị tất cả các phần tử bằng 0. Cho một dãy gồm ~q~ truy vấn, mỗi truy vấn có dạng ~a~ ~b~ ~k~ với ý nghĩa tăng giá trị các phần tử có vị trí từ ~a~ đến ~b~ lên ~k~ đơn vị.

Yêu cầu

Hãy cho biết giá trị lớn nhất của dãy ~X_1, X_2, \dots, X_n~ sau khi thực hiện lần lượt ~q~ truy vấn.

Input

• Dòng đầu ghi 2 số nguyên ~n~, ~q~.
• ~q~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên lần lượt là ~a~, ~b~, ~k~.

Output

Một số nguyên là giá trị lớn nhất của dãy số sau khi thực hiện ~q~ truy vấn.

Giới hạn:

• ~3 \leq n \leq 10^7~;
• ~1 \leq q \leq 2.10^5~;
• ~1 \leq a \leq b \leq n~;
• ~0 \leq k \leq 10^9~.

Sample Test

Input

5 3
1 2 100
2 5 100
3 4 100

Output

200