MianKing играет в игру. В этой игре у него есть $n$ насекомых, и каждое насекомое обладает двумя целочисленными атрибутами: тип и уровень. Тип и уровень $i$-го насекомого равны $type_i$ и $level_i$ соответственно.

Изначально каждое из этих $n$ насекомых имеет бафф «семя». Когда насекомое с баффом «семя» устраняется, пусть $L$ обозначает максимальный уровень среди оставшихся насекомых (с баффом «семя» или без него) того же типа, что и устраненное насекомое. Затем MianKing может произвольно выбрать целое число $D$ из диапазона $[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