环保绿化

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 trees.in 输出文件 trees.out

【问题描述】

一条街的一边有几座房子.因为环保原因居民想要在路边种些树.路边的地区被分割成 块,并被编号成1..N.每个部分为一个单位尺寸大小并最多可种一棵树.每个居民想在门 前种些树并指定了三个号码B,E,T.这三个数表示该居民想在B和E之间最少种T棵树.当 然,B≤E,居民必须记住在指定区不能种多于区域地块数的树,所以T≤E-B+l.居民们想 种树的各自区域可以交叉.你的任务是求出能满足所有要求的最少的树的数量.

【输入】

第一行包含数据N,表示区域的个数;

第二行包含H,表示房子的数目;

下面的H行描述居民们的需要:b e t(1<=b<=e<=30000,t<=e-b+1);

【输出】

输出文件仅有一行，写有树的数目。

【样例输入】

trees.in

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

【样例输出】

trees.out

5

 【数据规模】


30%的数据满足0<n<=1000,0<h<=500；


100%的数据满足n<=30000,h<=5000。