B. Стакан наполовину разлит
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На столе стоит $$$n$$$ стаканов, пронумерованных $$$1, \ldots, n$$$. В стакан $$$i$$$ может поместиться до $$$a_i$$$ единиц объёма воды, и сейчас этот стакан содержит $$$b_i$$$ единиц воды.

Вы хотите выбрать $$$k$$$ стаканов и собрать в них как можно больше воды. Для этого вы можете сколько угодно раз переливать воду из одного стакана в другой. Однако, из-за очень неудобной формы стаканов (а вовсе не из-за вашей неуклюжести), каждый раз, когда вы пытаетесь перелить любой объём воды, половина этого объёма проливается на пол.

Формально, пусть стакан $$$i$$$ сейчас содержит $$$c_i$$$ единиц воды, а стакан $$$j$$$ содержит $$$c_j$$$ единиц воды. Пускай вы пытаетесь переместить $$$x$$$ единиц из стакана $$$i$$$ в стакан $$$j$$$ (разумеется, $$$x$$$ не может превосходить $$$c_i$$$). Тогда $$$x / 2$$$ единиц воды проливается на пол. После переливания стакан $$$i$$$ будет содержать $$$c_i - x$$$ единиц воды, а стакан $$$j$$$ будет содержать $$$\min(a_j, c_j + x / 2)$$$ единиц (лишняя вода, которая не помещается в стакан, также проливается).

Для каждого переливания вы можете произвольно выбрать, из какого стакана $$$i$$$ в какой стакан $$$j$$$ надо переливать, а также переливаемый объём $$$x$$$ может быть произвольным вещественным числом.

Для каждого $$$k = 1, \ldots, n$$$ определите максимально возможный объём воды, который можно собрать в $$$k$$$ произвольно выбранных стаканах после нуля или более переливаний между стаканами.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1 \leq n \leq 100$$$) — количество стаканов.

Следующие $$$n$$$ строк описывают стаканы. В $$$i$$$-й из этих строк записано два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \leq b_i \leq a_i \leq 100$$$, $$$a_i > 0$$$) — вместимость и текущее количество воды в стакане $$$i$$$ соответственно.

Выходные данные

Выведите $$$n$$$ вещественных чисел — наибольший объём воды, который можно собрать в $$$1, \ldots, n$$$ стаканах соответственно. Ваш ответ будет принят, если каждое число находится в пределах $$$10^{-9}$$$ абсолютной или относительной погрешности от точного ответа.

Пример
Входные данные
3
6 5
6 5
10 2
Выходные данные
7.0000000000 11.0000000000 12.0000000000
Примечание

В примере можно действовать так:

  • Для $$$k = 1$$$ перельём всю воду из первых двух стаканов в третий. Мы прольём $$$(5 + 5) / 2 = 5$$$ единиц воды и соберём $$$2 + (5 + 5) / 2 = 7$$$ единиц.
  • Для $$$k = 2$$$ перельём всю воду из третьего стакана в любой из первых двух. Мы прольём $$$2 / 2 = 1$$$ единиц воды и соберём $$$5 + 5 + 2 / 2 = 11$$$ единиц.
  • Для $$$k = 3$$$ ничего не нужно делать. Все $$$5 + 5 + 2 = 12$$$ единиц воды уже собраны.