题目描述

sk 有 $N$ 个漂亮的盒子，编号为 $1\sim N$。第 $i$ 个盒子有两个属性 $S_i$ 和 $P_i$，分别表示这个盒子的大小和美丽程度。

如果 $S_i\le S_j$，则盒子 $i$ 可以被放入盒子 $j$ 中。

mxr 的生日快到了，sk 想送一些盒子作为礼物。不过只送空盒子显得不够有趣，所以 sk 想把一些盒子装进另一些盒子里。

具体来说，sk 会选择若干对盒子。对于每一对盒子，他会把其中一个盒子放进另一个盒子中：

• 如果两个盒子的大小不同，那么必须把较小的盒子放进较大的盒子中；
• 如果两个盒子的大小相同，那么可以任选一个放进另一个中。

若盒子 $i$ 被放入盒子 $j$ 中，则这一对盒子的美丽值为

这是因为 sk 认为放在里面的盒子的美丽程度被浪费了。

由于拆盒子很无聊，mxr 可能不想收到太多对盒子。sk 也不知道最理想的对数 $K$ 是多少。

因此，对于每个 $K=1,2,\ldots,\left\lfloor\frac N2\right\rfloor$，你需要求出：最多选择 $K$ 对互不重复使用的盒子时，能够得到的最大总美丽值。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含两个整数 $S_i,P_i$，表示第 $i$ 个盒子的大小和美丽程度。

输出格式

输出 $\left\lfloor\frac N2\right\rfloor$ 行。

第 $i$ 行输出当 $K=i$ 时，能够得到的最大总美丽值。

样例

输入

5
1 4
1 5
1 3
3 4
3 1

输出

3
5

数据范围

• 对于 $10\%$ 的数据，$N\le 10$；
• 对于 $30\%$ 的数据，$N\le 100$；
• 对于 $60\%$ 的数据，$N\le 2\times 10^3$；
• 对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$，$1\le S_i\le N$，$1\le P_i\le 10^9$。