MianKing 正在玩一個遊戲。在這個遊戲中，他有 $n$ 隻昆蟲，每隻昆蟲都有兩個整數屬性：類型（type）與等級（level）。第 $i$ 隻昆蟲的類型為 $type_i$，等級為 $level_i$。

最初，這 $n$ 隻昆蟲每一隻都有一個「種子」增益效果。當一隻帶有「種子」增益的昆蟲被消除時，令 $L$ 為剩餘同類型昆蟲（無論是否帶有種子增益）中的最高等級。接著，MianKing 可以任意選擇一個整數類型 $D \in [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