P3743 Little Bird's Devices

Little Bird has $n$ devices that can be used simultaneously. The $i$-th device consumes $a_i$ units of energy per second. Energy usage is continuous; that is, energy is not consumed instantaneously at a moment but at a constant rate. In other words, for any real number $k$, the amount of energy consumed in $k$ seconds is $k \times a_i$ units. Initially, the $i$-th device stores $b_i$ units of energy. Little Bird also has a power bank that can charge any one device, supplying $p$ units of energy per second. Charging is also continuous. You can charge any device at any time, and the time to switch from one device to another is negligible. Little Bird wants to use all these devices together until some device’s energy drops to $0$. Given the power bank, she wants to know the maximum duration she can keep all devices running together.

The first line contains two integers $n, p$. The next $n$ lines each describe one device, giving two integers: the device’s $a_i$ and $b_i$.

If Little Bird can use these devices indefinitely, output $-1$. Otherwise, output the maximum duration before some device’s energy becomes $0$. Let your answer be $a$ and the standard answer be $b$. You will receive full credit on a test point only if $a, b$ satisfy $\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}$.

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq p \leq 10^5$, $1 \leq a_i, b_i \leq 10^5$. Translated by ChatGPT 5