← 返回题目列表

Codeforces · 203/E

E. 运输

中文机器翻译题面 查看原题

Valera来到日本并购买了许多机器人用于他的研究。他已经到了机场,飞机很快就要起飞了,瓦莱拉迫切需要将所有机器人搬到行李舱。

这些机器人是自行式的(它们可以自行移动),其中一些甚至有隔间来携带其他机器人。更准确地说,对于第 i 个机器人,我们知道值 ci——它可以携带的机器人数量。在这种情况下,每个ci运输的机器人可以另外携带其他机器人。

然而,机器人需要加满燃料才能行驶,所以瓦莱拉花光了最后的钱,买了S升燃料。他了解到,每个机器人都有行驶距离的限制。因此,除了特征 ci 之外,第 i 个机器人还有两个特征 fi 和 li - 移动第 i 个机器人所需的燃料量(以升为单位),以及机器人可以行驶的最大距离。

由于时间和燃料有限,Valera 希望将最大数量的机器人移至行李舱。他的操作如下。

- 首先,Valera 选择一些能够自行前往行李舱的机器人。在这种情况下,移动所有这些机器人所需的燃料总量不得超过 S。
- 然后 Valera 将机器人放入隔间中,以便运输尽可能多的机器人。请注意,如果机器人本身不移动,您可以将其放入另一个由移动机器人直接或间接移动的不移动机器人中。
- 之后,所有选定并就座的机器人与 Valera 一起进入行李舱,其余机器人将丢失。

距离行李舱有 d 米。因此,将携带其余部分的机器人必须具有不小于 d 的特征 li。在移动过程中,瓦莱拉不能以任何方式停止或改变机器人的位置。

帮助瓦莱拉计算他最多可以带回家的机器人数量,以及他需要花费的最少燃料,因为剩余的燃料将在瓦莱拉的研究中派上用场。

输入

第一行包含三个空格分隔的整数 n、d、S (1 ≤ n ≤ 105, 1 ≤ d, S ≤ 109)。第一个数字代表机器人的数量,第二个数字代表到行李舱的距离,第三个数字代表可用燃料的量。

接下来的 n 行指定机器人。第 i 行包含三个空格分隔的整数 ci, fi, li (0 ≤ ci, fi, li ≤ 109) — 第 i 个机器人的特征。第一个数字是第 i 个机器人可以携带的机器人数量,第二个数字是第 i 个机器人移动所需的燃料量,第三个数字表示第 i 个机器人可以移动的最大距离。

输出

打印两个空格分隔的整数 - Valera 可以运送到行李舱的机器人的最大数量以及他为此所需的最小燃料量。如果瓦莱拉无法将任何机器人带到行李舱,请打印两个零。

示例

输入 #1

3 10 10
0 12 10
1 6 10
0 1 1

输出 #1

2 6

输入 #2

2 7 10
3 12 10
5 16 8

输出 #2

0 0

输入 #3

4 8 10
0 12 3
1 1 0
0 3 11
1 6 9

输出 #3

4 9