l. 街上的树

    Type: Default 1000ms 256MiB

街上的树

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

输入格式

第一行为 nn,表示路段数。

第二行为 hh,表示建议数。

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

输出格式

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

样例

样例输入

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

样例输出

5

数据范围与提示

30%30\% 的数据满足 0<n10000<n\le 10000<h5000<h\le 500

100%100\% 的数据满足 0<n3×1040<n\le 3\times 10^4h5000h\le 50000<be3×1040<b\le e\le 3\times 10^4teb+1t\le e-b+1

第七届SWPU-ACM新生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
103
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
58