Cho dãy ~A~ gồm ~n~ phần tử, ban đầu mọi phần tử bằng ~0~. Có ~Q~ lần cập nhật, mỗi lần cho ~u,v,M~ và cộng ~M~ vào mọi phần tử trong đoạn ~[u,v]~.

Yêu cầu

Sau tất cả cập nhật, tìm giá trị lớn nhất trong dãy.

Input

• Dòng đầu chứa hai số nguyên ~n,Q~ ~(1 \le n,Q \le 10^6)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u,v,M~ ~(1 \le u \le v \le n, M\ne 0, |M| \le 10^6)~.

Output

In ra giá trị lớn nhất trong dãy sau các cập nhật.

Subtask

• Có ~70\%~ số test với ~1 \le n,Q \le 10^3~.
• Có ~30\%~ số test với ~10^3 < n,Q \le 10^6~.

Ví dụ

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

6