MianKing은 게임을 하고 있습니다. 이 게임에서 그는 $n$마리의 곤충을 가지고 있으며, 각 곤충은 $type$과 $level$이라는 두 가지 정수 속성을 가집니다. $i$번째 곤충의 타입과 레벨은 각각 $type_i$와 $level_i$입니다.

처음에 이 $n$마리의 곤충은 모두 "씨앗(seed)" 버프를 가지고 있습니다. "씨앗" 버프가 있는 곤충이 제거되면, 제거된 곤충과 같은 타입의 남아있는 곤충들(씨앗 버프 유무와 관계없이) 중 가장 높은 레벨을 $L$이라고 합시다. 그러면 MianKing은 임의의 정수 타입 $D$를 $[1, n]$ 범위에서 선택하여 타입 $D$이고 레벨이 $L$인 새로운 곤충을 추가할 수 있습니다. 이 새로운 곤충은 "씨앗" 버프를 가지지 않습니다.

제거된 곤충과 같은 타입의 다른 곤충이 없다면 새로운 곤충을 추가할 수 없다는 점에 유의하십시오.

이제 MianKing은 일부 곤충을 제거하여 필드에 있는 모든 곤충의 총 레벨을 최대화하려고 합니다. 총 레벨은 개별 곤충들의 레벨 합입니다. 최대 $K$마리의 곤충을 제거하여 얻을 수 있는 최대 총 레벨인 $ans_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