Talent Show#10389
Farmer John is bringing his cows, conveniently numbered from to , to the county fair to compete in the annual bovine talent show! His -th cow has weight w_i and talent level t_i, both of which are integers.
Upon arrival, Farmer John is quite surprised by the new rules of this year's talent show:
The group of cows entered into the show must have a total weight of at least (to ensure that strong teams of cows compete, not just strong individuals).
The group with the largest ratio of total talent to total weight wins.
FJ observes that all of his cows together weigh at least , so he can always enter a team satisfying the first rule. Help him determine the best ratio of talent to weight he can achieve with such a team.
The first line contains two integers and W~(1 \le n \le 250, 1 \le W \le 1000). Each of the next lines describes one cow and contains two integers w_i and t_i~(1 \le w_i \le 10^6, 1 \le t_i \le 1000).
Let be the largest possible ratio of total talent to total weight that Farmer John can achieve with a group of cows of total weight at least . Print , that is, the value rounded down to an integer.
Example 1
In this example, the best talent-to-weight ratio overall would be achieved by using only the cow with talent and weight . However, since the total weight must be at least , the optimal solution is to use this cow together with the cow with talent and weight . This gives a talent-to-weight ratio of (11 + 21) / (10 + 20) = 32 / 30 = 1.0666\ldots, which, multiplied by and rounded down, gives .