Source : 一本通提高篇
Description

  一条街道的一边有几座房子。因为环境原因居民想要在路边种些树,路边的地区被分割成 nn 块,并被编号为 1n1…n,每块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数 b,e,tb,e,t,这三个数分别表示该居民想在 bbcc 之间最少要种 tt 棵树。当然,be,teb+1b≤e,t≤e-b+1,允许居民想种树的子区域可以交叉。处于资金紧缺的原因,环保部门请你求出能够满足所有居民的种树要求时所需要种的树的最少数量。

Input

  第一行为 nn,表示区域的个数。
  第二行为 hh,表示房子的数目。
  下面 hh 行描述居民的需要:bbeet(0<be30000,teb+1)t(0<b\leq e \leq 30000,t\leq e-b+1)分别用一个空格分开。

Output

  输出一个数,为满足所有居民的要求,所需要种树的最少数量。

Sample Input
9
4
1 4 2
4 6 2
8 9 2
3 5 2
Sample Output
5
Hint

  数据范围
  30%30\% 的数据满足 01000;05000≤1000;0≤500
  100%100\% 的数据满足 n30000,h5000n≤30000,h≤5000