TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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\)