Cho dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1,a_2,…,a_n~. Ban đầu tất cả các phần tử đều mang giá trị 0. Bạn cần thực hiện ~Q~ thao tác cập nhật trên dãy số này, với mỗi thao tác, cần tăng đoạn gồm các phần tử từ vị trí ~l~ tới vị trí ~r~ của dãy số thêm ~k~ đơn vị.

Yêu cầu: Tìm giá trị lớn nhất của dãy số sau khi thực hiện xong cả ~Q~ thao tác cập nhật?

Input:

Dòng đầu tiên chứa hai số nguyên dương

• ~n~ và ~Q~ - độ dài dãy số và số lượng thao tác cập nhật.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l~,~r~,~k~ thể hiện một thao tác cập nhật.

Ràng buộc:

• ~1 ≤ n,Q ≤ 10^5~.~1 ≤ k ≤ 10^9~.

• In ra giá trị lớn nhất của dãy số sau Q thao tác cập nhật.

Input:

5 4
1 4 3
2 5 3
1 5 10
2 2 1

Output:

17