Transportation

题意翻译

### 题目描述 Valera 来到了日本并为他的研究买了很多机器人。他已经在机场了，但是飞机马上起飞了！所以他现在急需要将所有机器人带到行李舱。 所有机器人都可以自行前进，甚至有一些机器人还带有可以携带其它机器人的行李舱！也就是说，第 $i$ 个机器人可以携带 $c_i$ 个机器人。这 $c_i$ 个被运输的机器人还可以携带其它机器人！ 但是无论如何，这些机器人前进都需要依靠燃料。所以 Valera 用它剩下的钱全部用来买了燃料，一共买到了 $S$ 升燃料。他知道每个机器人的前进距离都有限制。所以，除了 $c_i$ 这个属性之外，第 $i$ 个机器人还有两个属性，$f_i$ 和 $l_i$，也就是需要多少升燃料和这个机器人最远能走多远。 因为时间和燃料有限，Valera 想把尽可能多的机器人送进行李舱。他按如下步骤操作： - 首先 Valera 选择了一些自己就能前进到行李舱的机器人。在这种情况，运输这些机器人所耗费的总燃料数量不能超过 $S$。 - 接下来 Valera 将这些机器人放到了行李舱中，以便运送尽可能多的机器人。注意，如果一个机器人不自己移动，你也可以将它放进一个不自己移动但可以被直接或间接移动的机器人里。解释一下，只要最外面的机器人是移动的，那么它里面的机器人就可以移动，它里面的机器人里面的机器人也可以被移动，以此类推。 - 最后，所有在行李舱中放置的机器人都可以被 Valera 带走，但是剩下的机器人就留下了。 到行李舱一共有 $d$ 米，所以运输其他机器人的机器人的 $l_i$ 属性（能前进的最远距离）不能小于 $d$。在此过程中，Valera 不可以停止或改变任何一个机器人的位置。 请帮助 Valera 计算出他最多能将多少机器人带回家，和最少需要多少燃料。因为剩下的燃料被用在他的研究当中。 ### 输入格式 第一行包括3个整数 $n$，$d$，$S$ （1 <= $n$ <= $10^5$，1 <= $d$，$S$ <= $10^9$），分别是机器人数量、到行李舱的距离和燃料数量。 接下来 $n$ 行，输入机器人的具体属性。第 $i$ 行包括三个整数 $c_i$，$f_i$，$l_i$ （0 <= $c_i$，$f_i$，$l_i$ <= $10^9$），表示第 $i$ 个机器人的属性，分别表示能运输多少个机器人、需要多少升汽油、最远能走多远。 ### 输出格式 输出两个整数，表示 Valera 最多可以将多少机器人带进行李舱中和最少需要多少升燃料才能完成。如果可怜的 Valera 不能将任何一个机器人带进行李舱，输出两个零。 严格翻译题目，未加任何改动。

题目描述

Valera came to Japan and bought many robots for his research. He's already at the airport, the plane will fly very soon and Valera urgently needs to bring all robots to the luggage compartment. The robots are self-propelled (they can potentially move on their own), some of them even have compartments to carry other robots. More precisely, for the $ i $ -th robot we know value $ c_{i} $ — the number of robots it can carry. In this case, each of $ c_{i} $ transported robots can additionally carry other robots. However, the robots need to be filled with fuel to go, so Valera spent all his last money and bought $ S $ liters of fuel. He learned that each robot has a restriction on travel distances. Thus, in addition to features $ c_{i} $ , the $ i $ -th robot has two features $ f_{i} $ and $ l_{i} $ — the amount of fuel (in liters) needed to move the $ i $ -th robot, and the maximum distance that the robot can go. Due to the limited amount of time and fuel, Valera wants to move the maximum number of robots to the luggage compartment. He operates as follows. - First Valera selects some robots that will travel to the luggage compartment on their own. In this case the total amount of fuel required to move all these robots must not exceed $ S $ . - Then Valera seats the robots into the compartments, so as to transport as many robots as possible. Note that if a robot doesn't move by itself, you can put it in another not moving robot that is moved directly or indirectly by a moving robot. - After that all selected and seated robots along with Valera go to the luggage compartment and the rest robots will be lost. There are $ d $ meters to the luggage compartment. Therefore, the robots that will carry the rest, must have feature $ l_{i} $ of not less than $ d $ . During the moving Valera cannot stop or change the location of the robots in any way. Help Valera calculate the maximum number of robots that he will be able to take home, and the minimum amount of fuel he will have to spend, because the remaining fuel will come in handy in Valera's research.

输入输出格式

输入格式

The first line contains three space-separated integers $ n,d,S $ $ (1<=n<=10^{5},1<=d,S<=10^{9}) $ . The first number represents the number of robots, the second one — the distance to the luggage compartment and the third one — the amount of available fuel. Next $ n $ lines specify the robots. The $ i $ -th line contains three space-separated integers $ c_{i},f_{i},l_{i} $ $ (0<=c_{i},f_{i},l_{i}<=10^{9}) $ — the $ i $ -th robot's features. The first number is the number of robots the $ i $ -th robot can carry, the second number is the amount of fuel needed for the $ i $ -th robot to move and the third one shows the maximum distance the $ i $ -th robot can go.

输出格式

Print two space-separated integers — the maximum number of robots Valera can transport to the luggage compartment and the minimum amount of fuel he will need for that. If Valera won't manage to get any robots to the luggage compartment, print two zeroes.

输入输出样例

输入样例 #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