Talent Show

Farmer John brings his $N$ cows, numbered $1$ through $N$, to the county fair for the annual bovine talent show. Cow $i$ has weight $w_i$ and talent level $t_i$, both integers.

The rules of this year's show are new.

(i) The group of cows entered into the show must have total weight at least $W$. The rule exists so that one outstanding cow cannot win on its own.

(ii) The group with the largest ratio of total talent to total weight wins.

All of Farmer John's cows together weigh at least $W$, so a group satisfying rule (i) always exists. Determine the largest ratio of total talent to total weight he can reach with such a group.

The first line contains $N$ ($1 \le N \le 250$) and $W$ ($1 \le W \le 1000$). Each of the next $N$ lines describes one cow with two integers $w_i$ ($1 \le w_i \le 10^6$) and $t_i$ ($1 \le t_i \le 10^3$).

Let $A$ be the largest ratio of total talent to total weight reachable by a group whose total weight is at least $W$. Print the floor of $1000A$, which keeps the output integer. The floor operation discards the fractional part and rounds down to an integer, and leaves a value that is already an integer unchanged.

In the first example the best ratio for a single cow belongs to the cow with talent 11 and weight 10. The group needs total weight at least 15, so the best group adds the cow with talent 21 and weight 20. That group has ratio $(11+21)/(10+20) = 32/30 = 1.0666\ldots$, and multiplying by 1000 and taking the floor gives 1066.