一条街的一边有若干房子。路边被分成编号为 1,2,…,n 的单位区域，每个区域最多种一棵树。

每位居民给出 b、e、t，要求在区域 b 到 e（含端点）之间至少种 t 棵树。各居民指定的区域可以交叉。求满足全部要求所需的最少树木数量。

输入格式

第一行一个整数 n，表示区域数。

第二行一个整数 h，表示居民数。

接下来 h 行，每行三个整数 b_i,e_i,t_i。

输出格式

输出最少的树木数量。

样例输入

9
4
1 4 2
4 6 2
8 9 2
3 5 2

样例输出

5

数据范围

1 ≤ n ≤ 3×10^4，1 ≤ h ≤ 5×10^3；1 ≤ b_i ≤ e_i ≤ n，1 ≤ t_i ≤ e_i-b_i+1。

1
1
1 1 1

1

10
2
1 10 10
3 7 2

10

10
3
1 3 1
4 6 1
7 10 1

3