sk 有 $N$ 个漂亮的盒子，编号为 $1\sim N$。第 $i$ 个盒子有两个属性 $S_i$ 和 $P_i$，分别代表该盒子的大小和美丽程度。盒子 $i$ 能够被放入所有满足 $S_i\leq S_j$ 的盒子 $j$ 中。

mxr 的生日要来了，于是 sk 打算给 mxr 送一些盒子作为生日礼物。因为送空盒子听起来不是很好，所以 sk 打算在盒子里面装其他盒子。具体地，sk 打算选择 $K$ 对盒子，然后对每一对盒子，将某个盒子放到另一个里面（如果两个盒子的大小相同，他可以选择将哪个盒子放入另一个，否则他将小的那个盒子放入大的盒子中）。对每一对盒子 $(i,j)$，如果盒子 $i$ 在盒子 $j$ 中，那么这一对盒子的美丽值为 $P_j-P_i$，因为 sk 觉得里面的盒子的美丽程度被浪费了。

由于拆盒子是一件很无聊的事，所以 mxr 可能不想要太多对盒子，并且 sk 不知道最理想的 $K$ 值是多少。所以，对 $1$ 到 $\lfloor \frac{n}{2} \rfloor$ 之间的每个 $K$，你需要帮 sk 找到他能用最多 $K$ 对盒子得到的最高的总美丽值（即所有盒子对的美丽值之和的最大值）。

输入格式

第一行一个整数表示 $N$。

接下来 $N$ 行每行两个整数表示 $S_i,P_i$。

输出格式

输出 $\lfloor \frac{n}{2} \rfloor$行，第 $i$ 行表示 $k=i$ 时的答案。

样例一

input

5
1 4
1 5
1 3
3 4
3 1

output

3
5

限制与约定

对于 $10\%$ 的数据，$N\leq 10$。

对于 $30\%$ 的数据，$N\leq 100$。

对于 $60\%$ 的数据，$N\leq 2\times 10^3$。

对于 $100\%$ 的数据，$1\leq N \leq 2\times 10^5$，$1\leq S_i\leq n$，$1\leq P_i\leq 10^9$。