Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

В условии задачи недавно были сделаны правки. Просмотреть изменения.

×
E. Transportation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputValera 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.

Input

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.

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2020 08:56:44 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|