MianKing gra w grę, w której posiada $n$ owadów, a każdy z nich ma dwa atrybuty całkowite: typ i poziom. Typ i poziom $i$-tego owada to odpowiednio $type_i$ oraz $level_i$.

Początkowo każdy z tych $n$ owadów posiada wzmocnienie „ziarno” (ang. seed buff). Kiedy owad ze wzmocnieniem „ziarno” zostaje wyeliminowany, niech $L$ oznacza najwyższy poziom wśród pozostałych owadów (ze wzmocnieniem „ziarno” lub bez) tego samego typu, co wyeliminowany owad. Następnie MianKing może dowolnie wybrać liczbę całkowitą $D$ z zakresu $[1, n]$ i dodać nowego owada typu $D$ o poziomie $L$. Ten nowy owad nie posiada wzmocnienia „ziarno”.

Zauważ, że jeśli nie ma innych owadów tego samego typu co wyeliminowany owad, nie można dodać żadnego nowego owada.

MianKing chce zmaksymalizować łączny poziom wszystkich owadów na polu poprzez wyeliminowanie pewnych owadów. Łączny poziom to suma poziomów poszczególnych owadów. Musisz pomóc mu obliczyć $ans_K$, czyli maksymalny łączny poziom, jaki może uzyskać, eliminując co najwyżej $K$ owadów.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^5$).

Następnie następuje $n$ linii, gdzie $i$-ta linia zawiera dwie liczby całkowite $type_i$ oraz $level_i$ ($1 \le type_i \le n$, $1 \le level_i \le 10^7$).

Wyjście

Wypisz $n$ linii, tak aby $i$-ta linia zawierała jedną liczbę całkowitą $ans_i$.

Przykład

Wejście 1

4
1 5
1 6
2 2
3 1

Wyjście 1

15
20
24
24

Wejście 2

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

Wyjście 2

20
24
27
29
30
30

Wejście 3

4
1 1
2 2
3 3
4 4

Wyjście 3

10
10
10
10