题目描述

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

输入格式

第一行为n，表示区域的个数。
第二行为h，表示房子的数目。
下面h行描述居民的需要：b、e、t（0<b<=e<=30000,t<=e-b+1）分别用一个空格分开。

输出格式

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

样例输入

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

样例输出

5

Limitation

30%的数据满足0<n<=1000;0<h<=500.
100%的数据满足n<=30000;h<=5000。