Hinanai Tenshi’s peach garden

Hinanai Tenshi is managing a peach garden in Bhavagra. Due to the careful watch of Tenshi, the peach garden becomes a great view of Bhavagra. Once a famous person whose ear is pretty big said when visiting the garden: “This is peach garden?”

Another harvest season has come, Tenshi wants to move all the peaches to one point, so Tenshi sent her sidekick, Nagae Iku, to do this mission. However, Iku was only able to move all peaches to N points before she was sent to other missions…The remaining work can only be done by Tenshi herself.

Now Iku has moved the peaches to N points, the ith point is (xi, 0), which has pi peaches on it. Moving one peach from one point to another point costs the distance between these two points, two peaches is double the cost and etc. Tenshi wants to move as many peaches to one point as possible without costing too much, so Tenshi wants to know how many peaches can she move to one point without total costing over K.

Multiple test cases (no more than 20), for each case:
The first line contains two integers N and K (0<N<=10^4, 0<=K<=10^18).
Following N lines, each line contains two integers x_i and p_i (0<=x_i<10^9, 0<p_i<10^4).
Input terminates with EOF.

For each cast output one integer, representing the number of peaches she can move to one place at most.

3 1
0 1
1 1
2 1

2

temperlsyer

2011 Multi-University Training Contest 5 - Host by BNU