Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

#1001. 「一本通 1.1 例 2」种树

统计

题目描述

某条街被划为 $ n $ 条路段,这 $ n $ 条路段依次编号为$1 \cdots n $ 。每个路段最多可以种一棵树。现在居民们给出了 $ h $ 组建议,每组建议包含三个整数$ b,e,t $ ,表示居民希望在路段 $b$ 到 $e$ 之间至少要种 $t$ 棵树。这些建议所给路段的区间可以交叉。请问:如果要满足所有居民的建议,至少要种多少棵树。

输入格式

第一行为 $ n $,表示路段数。

第二行为 $ h $ ,表示建议数。

下面 $ h $ 行描述一条建议:$ b,e,t $,用一个空格分隔。

输出格式

输出只有一个数,为满足所有居民的建议,所需要种树的最少数量。

样例输入

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

样例输出

5

数据范围与提示

$30\%$的数据满足$ 0 \le n \leq 1000 $,$ 0 \le h \leq 500 $;

$100\%$的数据满足 $ 0 \le n \leq 3 \times 10^{4} $, $ h \leq 5000$, $0 \le b \leq e \leq 3 \times 10^{4} $ , $ t \leq e - b + 1$ 。