MianKing está jugando un juego. En este juego, tiene $n$ insectos, y cada insecto tiene dos atributos enteros: tipo y nivel. El tipo y el nivel del $i$-ésimo insecto son $type_i$ y $level_i$, respectivamente.

Inicialmente, cada uno de estos $n$ insectos tiene un beneficio de "semilla" (seed buff). Cuando se elimina un insecto con un beneficio de "semilla", sea $L$ el nivel más alto entre los insectos restantes (con o sin el beneficio de semilla) del mismo tipo que el insecto eliminado. Entonces, MianKing puede elegir un tipo entero $D$ de $[1, n]$ arbitrariamente y añadir un nuevo insecto de tipo $D$ y nivel $L$. Este nuevo insecto no tiene el beneficio de "semilla".

Nótese que si no hay otros insectos del mismo tipo que el insecto eliminado, no se puede añadir ningún insecto nuevo.

Ahora, MianKing quiere maximizar el nivel total de todos los insectos en el campo eliminando algunos insectos. El nivel total es la suma de los niveles de los insectos individuales. Debes ayudarle a calcular $ans_K$, el nivel total máximo que puede obtener eliminando como máximo $K$ insectos.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 10^5$).

Luego hay $n$ líneas, donde la $i$-ésima línea contiene dos enteros $type_i$ y $level_i$ ($1 \le type_i \le n$, $1 \le level_i \le 10^7$).

Salida

Imprime $n$ líneas, de tal manera que la $i$-ésima línea contenga un entero $ans_i$.

Ejemplos

Entrada 1

4
1 5
1 6
2 2
3 1

Salida 1

15
20
24
24

Entrada 2

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

Salida 2

20
24
27
29
30
30

Entrada 3

4
1 1
2 2
3 3
4 4

Salida 3

10
10
10
10