Description

Farmer John is taking his $n$ cows, conveniently numbered $1 \ldots n$, to the agricultural fair to participate in the annual Talent Show. His $i$-th cow has weight $w_i$ and talent $t_i$, both integers.

Upon arrival, Farmer John is alarmed by the new rules for this year's show:

(1) A participating group of cows must have total weight at least $W$ (this is to ensure strong teams compete, not just a single strong cow), and

(2) The group with the maximum ratio of total talent to total weight wins.

FJ notices that the total weight of all his cows is at least $W$, so he can send a team that satisfies rule (1). Help him determine the best achievable ratio of total talent to total weight among such teams.

Input Format

The first line contains two integers, the number of cows $n$ and the weight threshold $W$.

Lines $2$ through $(n+1)$ each contain two integers. The integers on line $(i+1)$ give the weight $w_i$ and talent $t_i$ of the $i$-th cow.

Output Format

Compute the maximum possible ratio of total talent to total weight for a group of cows whose total weight is at least $W$.

If your answer is $A$, output the value of $1000A$ rounded down to an integer (i.e., take the floor; when a number is not an integer, flooring removes all fractional digits).

Note that if the exact answer is an integer $x$, your program may produce $x - \epsilon$ due to floating-point precision and, after flooring, incorrectly output $x - 1$. In this case, you can add a tiny value before flooring, e.g., $x \gets x + 10^{-k}$, to avoid this issue.

3 15
20 21
10 11
30 31

1066

Hint

Sample Explanation

In this example, the globally best ratio of talent to weight would be achieved by using only the cow with talent $11$ and weight $10$. However, since we need at least $15$ units of weight, the optimal solution is to use that cow together with the cow of talent $21$ and weight $20$. The resulting ratio is $\frac{11+21}{10+20}=\frac{32}{30} = 1.0666\dots$, which becomes $1066$ after multiplying by $1000$ and taking the floor.

Constraints

For all testdata, it is guaranteed that $1 \leq n \leq 250$, $1 \leq W \leq 1000$, $1 \leq w_i \leq 10^6$, and $1 \leq t_i \leq 10^3$.

Translated by ChatGPT 5