一条街的一边有若干房子。路边被分成编号为 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
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

数据范围

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