1423：【例题2】种树

时间限制: 1000 ms
内存限制: 65536 KB
提交数: 9978
通过数: 4438

题目描述

现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成 $1..N$。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码 $B$，$E$，$T$。这三个数表示该居民想在 $B$ 和 $E$ 之间最少种 $T$ 棵树。当然，$B \le E$，居民必须记住在指定区不能种多于区域地块数的树，所以 $T \le E - B + 1$。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量减少政府的支出。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示区域的个数和房子的数目（$0 < N \le 30000$，$0 < M \le 5000$）。

接下来的 $M$ 行，每行三个整数 $B$, $E$, $T$，表示一个居民的要求：在区间 $[B, E]$ 内至少种 $T$ 棵树（$0 < 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