| VK Cup 2017 - Раунд 2 |
|---|
| Закончено |
У вас есть n гаджетов, которые вы хотите использовать одновременно.
Гаджет номер i использует ai единиц энергии в секунду. Это использование энергии непрерывное, то есть, за λ секунд гаджет использует λ·ai единиц энергии. Гаджет номер i сейчас имеет bi единиц энергии. Все устройства могут хранить неограниченное количество единиц энергии.
У вас есть единственное зарядное устройство, которое можно подключить к любому из гаджетов. Зарядное устройство заряжает подключенный гаджет на p единиц энергии в секунду. Зарядка происходит непрерывно, то есть, за λ секунд зарядки любой гаджет получит λ·p единиц энергии. Вы можете подключать зарядное устройство к любому гаджету в любой момент времени (в том числе, в нецелые моменты времени), можно считать, что переключение происходит мгновенно.
Вы задались вопросом: как долго вы можете использовать все гаджеты, прежде чем в каком-то из них останется 0 единиц энергии?
Если вы можете использовать гаджеты бесконечно долго, выведите -1. Иначе выведите максимально возможное время, в течение которого во всех гаджетах будет больше 0 единиц энергии.
Первая строка содержит два целых числа n и p (1 ≤ n ≤ 100 000, 1 ≤ p ≤ 109) — количество гаджетов и мощность зарядного устройства.
После этого следуют n строк, каждая из которых содержит два целых числа. Строка номер i содержит числа ai и bi (1 ≤ ai, bi ≤ 100 000) — мощность устройства и запас энергии в устройстве в начальный момент времени.
Если вы можете использовать гаджеты бесконечно долго, выведите -1. Иначе выведите максимально возможное время, в течение которого во всех гаджетах будет больше 0 единиц энергии.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит 10 - 4.
А именно, пусть ваш ответ равен a, а ответ жюри равен b. Ваш ответ будет засчитан, если 
.
2 1
2 2
2 1000
2.0000000000
1 100
1 1
-1
3 5
4 3
5 2
6 1
0.5000000000
В первом примере можно заряжать первый гаджет все время, пока в нем кончится энергия. Во втором гаджете достаточно энергии, чтобы работать все это время без подзарядки.
Во втором примере вы можете использовать гаджет бесконечно долго.
В третьем примере можно заряжать третий гаджет в течение 2 / 5 секунды, а затем заряжать второй гаджет еще 1 / 10 секунды.
