곤충

시간 제한1초메모리 제한256 MB

요약

씨앗 버프가 있는 곤충을 최대 i마리 제거하고, 제거한 곤충과 같은 종류의 남은 최고 레벨로 새 곤충을 추가할 때 전체 레벨 합의 최댓값을 i마다 구합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 해시맵, 누적 합
정답자: 아직 제출이 없습니다

문제

MianKing은 게임을 하고 있다. 그에게는 곤충 $n$ 마리가 있고, 각 곤충에는 종류(type)와 레벨(level)이라는 두 정수 속성이 있다. $i$ 번째 곤충의 종류는 $\mathit{type}_i$ , 레벨은 $\mathit{level}_i$ 이다.

처음에 이 $n$ 마리의 곤충은 모두 "seed" 버프를 받은 상태이다. "seed" 버프가 있는 곤충이 제거되면, 제거된 곤충과 같은 종류의 나머지 곤충(seed 버프 유무와 관계없이) 중 가장 높은 레벨을 $L$ 이라 하자. 그러면 MianKing은 $[1, n]$ 범위의 정수 $D$ 를 임의로 골라, 종류가 $D$ 이고 레벨이 $L$ 인 새 곤충을 추가할 수 있다. 새 곤충에는 "seed" 버프가 없다.

제거된 곤충과 같은 종류의 다른 곤충이 없으면 새 곤충을 추가할 수 없다.

MianKing은 일부 곤충을 제거해서 필드 위 모든 곤충 레벨의 합을 최대로 만들려고 한다. 레벨의 합은 개별 곤충 레벨들의 총합이다. 각 $i$ 에 대해, 최대 $i$ 마리까지 제거해서 얻을 수 있는 레벨 합의 최댓값을 $ans_i$ 라 하자.

입력

첫 줄에 정수 $n$ ( $1 \leq n \leq 10^5$ )이 주어진다.

이어지는 $n$ 개의 줄에는 각각 두 정수 $\mathit{type}_i$ 와 $\mathit{level}_i$ ( $1 \leq \mathit{type}_i \leq n$ , $1 \leq \mathit{level}_i \leq 10^7$ )가 주어진다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 정수 $ans_i$ 를 출력한다.

예제3

예제 1
입력
```
4
1 5
1 6
2 2
3 1
```
예상 출력
```
15
20
24
24
```

예제 2

입력

예상 출력

예제 3
입력
```
4
1 1
2 2
3 3
4 4
```
예상 출력
```
10
10
10
10
```