Description

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

Input Format

第一行为n ，表示路段数。

第二行为h ，表示房子的数。

下面 h 行描述一条建议：b，e,t用一个空格分隔。

n<=10000,h<=2000

Output Format

输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。

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

5

Source

贪心