MianKing はゲームをプレイしています。このゲームには $n$ 匹の昆虫がおり、各昆虫は「種類 (type)」と「レベル (level)」という2つの整数属性を持っています。$i$ 番目の昆虫の種類とレベルはそれぞれ $type_i$ と $level_i$ です。

最初、これら $n$ 匹の昆虫はすべて「種 (seed)」バフを持っています。「種」バフを持つ昆虫が排除されるとき、排除された昆虫と同じ種類の残りの昆虫（「種」バフの有無を問わない）の中で最も高いレベルを $L$ とします。その後、MianKing は $[1, n]$ の範囲から任意の整数 $D$ を種類として選び、種類 $D$、レベル $L$ の新しい昆虫を1匹追加できます。この新しい昆虫は「種」バフを持ちません。

排除された昆虫と同じ種類の他の昆虫が存在しない場合、新しい昆虫は追加できないことに注意してください。

MianKing は、いくつかの昆虫を排除することで、フィールド上のすべての昆虫のレベルの合計を最大化したいと考えています。合計レベルとは、個々の昆虫のレベルの総和です。最大 $K$ 匹の昆虫を排除することで得られる最大合計レベル $ans_K$ を計算してください。

入力

1行目に整数 $n$ ($1 \le n \le 10^5$) が与えられます。

続く $n$ 行には、各昆虫の情報として2つの整数 $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