说明

蒟蒻队长家里有 $n$ 个精致的玻璃杯，第 $i$ 个玻璃杯的容量为 $a_i$ 毫升，一开始装有 $b_i$ 毫升的水

最近蒟蒻队长学习了搜索的经典题目——《倒水》，于是他决定也把这些玻璃杯里的水倒一倒

但是显然，人的操作并没有办法达到题目中那么理想，在倒水的过程中还是会撒掉一部分水，这里我们简单的认为每次倒水会撒掉一半水

例如第 $x$ 个玻璃杯现在装有 $now_x$ 毫升水，第 $y$ 个玻璃杯装有 $now_y$ 毫升水

我们可以任意选择将 $x$ 杯中的 $z(z \leq b_x)$ 毫升水倒入 $y$ 杯中去

那么第 $x$ 个玻璃杯会剩下 $now_x - z$ 毫升水
而第 $y$ 个玻璃杯将会得到 $z / 2$ 毫升水，也就是最终 $y$ 玻璃杯中会有 $min(a_y, now_y + z / 2)$ 毫升水

现在蒟蒻队长想知道，如果他最后只选择 $m$ 个玻璃杯装水，其他玻璃杯全部倒空，怎么选这 $m$ 个玻璃杯可以使得水量最多？

输入格式

输入第一行包含一个整数 $n$ 表示玻璃杯数量

接下来 $n$ 行，每行两个整数 $a_i,b_i$，含义如题

测试点编号	$n$	特殊性质
$1 \sim 2$	$n \leq 50$	$a_i=b_i$
$3 \sim 4$	$n \leq 20$
$5 \sim 6$	$n \leq 50$	答案一定为整数(例如 $10.0$)
$7 \sim 10$	$n \leq 50$

对于 $100\%$ 的数据有：$1 \leq n \leq 50, 0 \leq b_i \leq a_i \leq 100$
</span>

输出格式

输出一行包含 $n$ 个实数，第 $i$ 个数字表示 $m = i$ 时能留下的最多水量，输出保留一位小数

3
6 5
6 5
10 2

7.0 11.0 12.0

来源

CSP模拟赛