MianKing joue à un jeu. Dans ce jeu, il possède $n$ insectes, et chaque insecte possède deux attributs entiers : le type et le niveau. Le type et le niveau du $i$-ième insecte sont respectivement $type_i$ et $level_i$.

Initialement, chacun de ces $n$ insectes possède un bonus « graine ». Lorsqu'un insecte avec un bonus « graine » est éliminé, soit $L$ le niveau le plus élevé parmi les insectes restants (avec ou sans le bonus « graine ») du même type que l'insecte éliminé. Ensuite, MianKing peut choisir arbitrairement un type entier $D$ dans $[1, n]$ et ajouter un nouvel insecte de type $D$ et de niveau $L$. Ce nouvel insecte ne possède pas le bonus « graine ».

Notez que s'il n'y a aucun autre insecte du même type que l'insecte éliminé, aucun nouvel insecte ne peut être ajouté.

Maintenant, MianKing souhaite maximiser le niveau total de tous les insectes sur le terrain en éliminant certains insectes. Le niveau total est la somme des niveaux des insectes individuels. Vous devez l'aider à calculer $ans_K$, le niveau total maximal qu'il peut obtenir en éliminant au plus $K$ insectes.

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 10^5$).

Ensuite, il y a $n$ lignes, où la $i$-ième ligne contient deux entiers $type_i$ et $level_i$ ($1 \le type_i \le n$, $1 \le level_i \le 10^7$).

Sortie

Affichez $n$ lignes, de sorte que la $i$-ième ligne contienne un entier $ans_i$.

Exemples

Entrée 1

4
1 5
1 6
2 2
3 1

Sortie 1

15
20
24
24

Entrée 2

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

Sortie 2

20
24
27
29
30
30

Entrée 3

4
1 1
2 2
3 3
4 4

Sortie 3

10
10
10
10