#2397. 庙会捷运

庙会捷运

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

公交车一共经过N\red{N(}1<=N<=20000\red{1<=N<=20000)}个站点,从站点1\red{1}一直驶到站点N\red{N}K\red{K(}1<=K<=50000)\red{1<=K<=50000)}群奶牛希望搭乘这辆公交车。

i\red{i}群牛一共有Mi\red{Mi(}1<=Mi<=N)\red{1<=Mi<=N)}只.他们希望从Si\red{Si}Ei\red{Ei}去。

公交车只能座C\red{C(}1<=C<=100\red{1<=C<=100)}只奶牛。而且不走重复路线,请计算这辆车最多能满足多少奶牛听要求。

注意:对于每一群奶牛,可以部分满足,也可以全部满足,也可以全部不满足。

输入格式

1\red{1}行: 三个整数: K\red{K,}N\red{N,}C\red{C}。 由空格隔开。

2..K+1\red{2..K+1}行:第i+1\red{i+1}行,告诉你第i\red{i}组奶牛的信息: Si,Ei\red{S_i, E_i}Mi\red{M_i}。由空格隔开。

输出格式

第一行:可以在庙会乘坐捷运的牛的最大头数

样例

输入样例

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

输出样例

10

提示

捷运可以把2\red{2}头奶牛从展台1\red{1}送到展台5\red{5,}3\red{3}头奶牛从展台5\red{5}到展台8\red{8,} 2\red{2}头奶牛从展台8\red{8 }到展台14\red{14,}1\red{1}头奶牛从展台9\red{9}送到展台12\red{12,}一头奶牛从展台13\red{13}送到展台14\red{14,} 一头奶牛从 14\red{14}送到15\red{15}

数据结构3

未参加
状态
已结束
规则
IOI
题目
19
开始于
2023-1-9 12:00
结束于
2023-1-17 20:00
持续时间
200 小时
主持人
参赛人数
12