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

Input format

The first line of input contains 3 numbers, N and Q. The next Q lines of input specify Li, Ri, and Si.

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

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Random idea (AlphanumericUsername)

Subtask Score
1 100
2 0