TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5222
  • 题目
  • P5222种树
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,256m
    问题描述

    某条街被划为 \(n\) 条路段,这 \(n\) 条路段依次编号为 $1\dots 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 < n \le 1000$,$0 < h \le 500$;

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