CF1458B.Glass Half Spilled

There are $n$ glasses on the table numbered $1, \ldots, n$. The glass $i$ can hold up to $a_i$ units of water, and currently contains $b_i$ units of water.

You would like to choose $k$ glasses and collect as much water in them as possible. To that effect you can pour water from one glass to another as many times as you like. However, because of the glasses' awkward shape (and totally unrelated to your natural clumsiness), each time you try to transfer any amount of water, half of the amount is spilled on the floor.

Formally, suppose a glass $i$ currently contains $c_i$ units of water, and a glass $j$ contains $c_j$ units of water. Suppose you try to transfer $x$ units from glass $i$ to glass $j$ (naturally, $x$ can not exceed $c_i$). Then, $x / 2$ units is spilled on the floor. After the transfer is done, the glass $i$ will contain $c_i - x$ units, and the glass $j$ will contain $\min(a_j, c_j + x / 2)$ units (excess water that doesn't fit in the glass is also spilled).

Each time you transfer water, you can arbitrarlly choose from which glass $i$ to which glass $j$ to pour, and also the amount $x$ transferred can be any positive real number.

For each $k = 1, \ldots, n$, determine the largest possible total amount of water that can be collected in arbitrarily chosen $k$ glasses after transferring water between glasses zero or more times.

桌子上有 $n$ 个编号为 $1, \ldots, n$ 的杯子。杯子 $i$ 最多可盛放 $a_i$ 单位的水，当前盛有 $b_i$ 单位的水。

你希望从中选出 $k$ 个杯子，并尽可能多地将水汇集到这 $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$ 可以是任意大于 0 的实数。

对每个 $k = 1, \ldots, n$，求出：经过零次或多次杯子间倒水操作后，能在任意选定的 $k$ 个杯子中汇集到的最大总水量。

The first line contains a single integer $n$ ($1 \leq n \leq 100$) — the number of glasses.

The following $n$ lines describe the glasses. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($0 \leq b_i \leq a_i \leq 100$, $a_i \gt 0$) — capacity, and water amount currently contained for the glass $i$, respectively.

第一行包含一个整数 $n$（$1 \leq n \leq 100$）——玻璃杯的数量。

接下来的 $n$ 行描述这些玻璃杯。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$0 \leq b_i \leq a_i \leq 100$，且 $a_i \gt 0$）——分别表示第 $i$ 个玻璃杯的容量和当前所盛水量。

Print $n$ real numbers — the largest amount of water that can be collected in $1, \ldots, n$ glasses respectively. Your answer will be accepted if each number is within $10^{-9}$ absolute or relative tolerance of the precise answer.

输出 $n$ 个实数——分别为在第 $1, \ldots, n$ 个杯子中所能收集到的最大水量。若每个数与精确答案的绝对误差或相对误差均在 $10^{-9}$ 范围内，则你的答案将被接受。

In the sample case, you can act as follows:

• for $k = 1$, transfer water from the first two glasses to the third one, spilling $(5 + 5) / 2 = 5$ units and securing $2 + (5 + 5) / 2 = 7$ units;
• for $k = 2$, transfer water from the third glass to any of the first two, spilling $2 / 2 = 1$ unit and securing $5 + 5 + 2 / 2 = 11$ units;
• for $k = 3$, do nothing. All $5 + 5 + 2 = 12$ units are secured.

在样例中，你可以按如下方式操作：

• 当 $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$ 单位均被保留。