Transportation

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.