Xét một xâu có chiều dài ~N~ bao gồm các chữ số 0 và 1. Điểm của xâu được tính như sau:

• Với mỗi số nguyên ~i~ (~1~ ≤ ~i~ ≤ ~M~), tổng số điểm của xâu được tăng thêm ~a_i~ nếu như xâu con bao gồm các kí tự từ ~l_i~ đến ~r_i~ (kể cả biên) có ít nhất một kí tự 1.

Với mọi xâu độ dài ~N~, số điểm cao nhất có thể đạt được là bao nhiêu?

Input

• Dòng đầu chứa hai số nguyên ~N, M~ (~1 \le N \le 2 \cdot 10^5~ và ~1 \le M \le 2 \cdot 10^5~).
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~l_i, r_i, a_i~ (~1 \le l_i \le r_i \le N~ và ~\mid a_i\mid \le 10^9~).

Output

Số điểm tối đa mà xâu có thể đạt được.

Sample 1

Input

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

Output

20

Giải thích

Điểm cho xâu 10001 là ~a_1 + a_3 = 10 + 10 = 20~.

Sample 2

Input

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

Output

90

Giải thích

Điểm cho xâu 100 là ~a_1 + a_2 = 100 + (-10) = 90~.

Sample 3

Input

1 1
1 1 -10

Output

0

Giải thích

Điểm cho xâu 0 là ~0~.

Sample 4

Input

1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

Output

5000000000

Kết quả có thể không phù hợp với số nguyên có định dạng 32-bit.

Sample 5

Input

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

Output

10

Giải thích

Điểm cho xâu 101000 là ~a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10~.