Problem3545--Transportation

3545: Transportation

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ci − the number of robots it can carry. In this case, each of ci 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 ci, the i-th robot has two features fi and li − 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 li 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.

Input

The first line contains three space-separated integers n,d,S (1≤n≤105,1≤d,S≤109). 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 ci,fi,li (0≤ci,fi,li≤109) − 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.

Output

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.

Examples
Input
3 10 10
0 12 10
1 6 10
0 1 1
Output
2 6
Input
2 7 10
3 12 10
5 16 8
Output
0 0
Input
4 8 10
0 12 3
1 1 0
0 3 11
1 6 9
Output
4 9

Source/Category

 
[Submit] [Status]