题目描述

桌上有 $n$ 个玻璃杯，编号为 $1, \ldots, n$。第 $i$ 个玻璃杯最多可以容纳 $a_i$ 单位的水，目前其中有 $b_i$ 单位的水。

你希望选择 $k$ 个玻璃杯，并在它们中收集尽可能多的水。为此，你可以任意多次地将水从一个杯子倒到另一个杯子中。然而，由于杯子的奇怪形状（绝对不是因为你的笨拙），每次你尝试转移任意数量的水时，一半的水都会洒到地上。

具体来说，假设某个玻璃杯 $i$ 目前有 $c_i$ 单位的水，玻璃杯 $j$ 有 $c_j$ 单位的水。你尝试从玻璃杯 $i$ 向玻璃杯 $j$ 倒 $x$ 单位的水（显然 $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$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$0 \leq b_i \leq a_i \leq 100$，$a_i > 0$），分别表示第 $i$ 个玻璃杯的容量和当前水量。

输出格式

输出 $n$ 个实数，分别表示在 $1, \ldots, n$ 个玻璃杯中能够收集到的最大水量。你的答案只要每个数与精确答案的绝对误差或相对误差不超过 $10^{-9}$ 即可被接受。

说明/提示

在样例中，你可以这样操作：

2. 对于 $k = 1$，将前两个玻璃杯的水全部倒入第三个杯子，会洒掉 $(5 + 5) / 2 = 5$ 单位的水，最终第三个杯子中有 $2 + (5 + 5) / 2 = 7$ 单位的水；
3. 对于 $k = 2$，将第三个杯子的水倒回前两个中的任意一个，会洒掉 $2 / 2 = 1$ 单位的水，最终可以收集到 $5 + 5 + 2 / 2 = 11$ 单位的水；
4. 对于 $k = 3$，无需操作，所有 $5 + 5 + 2 = 12$ 单位的水都可以收集到。

由 ChatGPT 4.1 翻译

样例

3
6 5
6 5
10 2

7.0000000000 11.0000000000 12.0000000000