boxes3

There are N (1<=N<=1,000,000,000) spaces. Given Q (1<=Q<=200,000) operations, add one box of size S_i to all spaces from L_i to R_i. At the end of all operations, how many spaces have boxes that are strictly decreasing from top to bottom? (1<=L_i<=R_i<=N, 1<=S_i<=1,000,000,000)

Input format

The first line of input contains 3 numbers, N and Q. The next Q lines of input specify L_i, R_i, and S_i.

Output format

Output 1 integer, the number of spaces which have boxes above it that are strictly decreasing from top to bottom. Note: empty spaces are NOT counted in the final answer

Sample input

4 2
1 3 1
2 4 2

Sample output

2