题目描述

现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成 $1$,$2$,$3$,...,$n$ 。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民房子门前被指定了三个号码 $b$，$e$，$t$ 。这三个数表示该居民想在 $b$ 和 $e$ 之间最少种 T 棵树。当然，B ≤ E ，居民必须记住在指定区不能种多于区域地块数的树，所以 $t \le e-b+1$ 。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量较少政府的支出。

输入格式

第一行包含数据 $n$，$m$，分别代表区域的个数 ( $0 \lt n \le 30000$ ) 和房子的数目 ( $0 \lt m \le 5000$ )；

下面的 $m$ 行描述居民们的需要：$b$ , $e$ , $t$ ( $0 \lt b \le e \le 30000$ ， $t \le e-b+1$ ) 。

输出格式

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

样例

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

5