P17456 [GESP202609 Level 5] Beverage Mixing.

You want to mix a beverage with exactly the right sweetness for your friends to taste. There are $n$ kinds of ingredients available for mixing the beverage. The remaining amount of the $i$-th ingredient is $v_i$ liters, and each liter contains $s_i$ grams of sugar. You may freely choose ingredients to add to the beverage, but the amount used for each ingredient must not exceed its remaining amount. That is, if you use $k_i$ liters of the $i$-th ingredient, then $0\le k_i\le v_i$. The value $k_i$ can be any number between $0$ and $v_i$ (including decimals). A beverage with exactly the right sweetness must have sweetness exactly equal to $t$. The sweetness of the final beverage you mix will be $\frac{\sum_{i=1}^{n}k_i\cdot s_i}{\sum_{i=1}^{n}k_i}$. To let more friends drink the beverage, ask what is the maximum number of liters of beverage with exactly the right sweetness that can be mixed. If it is impossible to mix a beverage with exactly the right sweetness, then the answer is considered to be $0$.

The first line contains two integers $n,t$, representing the number of ingredient types and the exactly-right sweetness. The next $n$ lines each contain two integers $v_i,s_i$, representing the remaining volume of the $i$-th ingredient and the sugar mass contained per liter.

Output one line with a decimal number, representing the maximum volume of beverage that can be mixed with exactly the right sweetness, rounded to three decimal places.

For $40\%$ of the test points, it is guaranteed that $n=2$. For all test points, it is guaranteed that $1\le n\le 2000$, $0\le t\le 200$, $1\le v_i\le 100$, $0\le s_i\le 200$. Translated by ChatGPT 5