MianKing 正在玩一个游戏。在这个游戏中，他有 $n$ 只昆虫，每只昆虫有两个整数属性：类型（type）和等级（level）。第 $i$ 只昆虫的类型为 $type_i$，等级为 $level_i$。

最初，这 $n$ 只昆虫每只都有一个“种子”增益。当一只带有“种子”增益的昆虫被消除时，令 $L$ 表示剩余的同类型昆虫（无论是否有“种子”增益）中的最高等级。随后，MianKing 可以任意选择一个整数类型 $D \in [1, n]$，并添加一只类型为 $D$、等级为 $L$ 的新昆虫。这只新昆虫没有“种子”增益。

注意，如果被消除的昆虫所属类型没有其他昆虫，则无法添加新昆虫。

现在，MianKing 想要通过消除一些昆虫来最大化场上所有昆虫的等级总和。等级总和即为所有个体昆虫等级之和。你需要帮他计算 $ans_K$，即通过消除最多 $K$ 只昆虫所能获得的最大等级总和。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $type_i$ 和 $level_i$ ($1 \le type_i \le n, 1 \le level_i \le 10^7$)。

输出格式

输出 $n$ 行，其中第 $i$ 行包含一个整数 $ans_i$。

样例

输入 1

4
1 5
1 6
2 2
3 1

输出 1

15
20
24
24

输入 2

6
1 1
2 2
3 3
4 4
5 5
5 5

输出 2

20
24
27
29
30
30

输入 3

4
1 1
2 2
3 3
4 4

输出 3

10
10
10
10