题目描述

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成n块，并被编号成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

数据规模与约定

n≤30000

h≤5000