TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5222
  • Problem
  • P5222种树
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,256m
    Description

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

    Input Format

    第一行为 \(n\),表示路段数。

    第二行为 \(h\),表示建议数。

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

    Output Format

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

    Sample Input

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

    Sample Output

    5

    Hint

    $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\)