MianKing đang chơi một trò chơi. Trong trò chơi này, anh ấy có $n$ con côn trùng, và mỗi con côn trùng có hai thuộc tính nguyên: loại (type) và cấp độ (level). Loại và cấp độ của con côn trùng thứ $i$ lần lượt là $type_i$ và $level_i$.

Ban đầu, mỗi con trong số $n$ con côn trùng này đều có một bùa "hạt giống" (seed). Khi một con côn trùng có bùa "hạt giống" bị loại bỏ, gọi $L$ là cấp độ cao nhất trong số các con côn trùng còn lại (có hoặc không có bùa "hạt giống") cùng loại với con côn trùng vừa bị loại bỏ. Sau đó, MianKing có thể chọn tùy ý một số nguyên $D$ thuộc đoạn $[1, n]$ và thêm một con côn trùng mới thuộc loại $D$ với cấp độ $L$. Con côn trùng mới này sẽ không có bùa "hạt giống".

Lưu ý rằng nếu không còn con côn trùng nào cùng loại với con côn trùng vừa bị loại bỏ, sẽ không có con côn trùng mới nào được thêm vào.

Hiện tại, MianKing muốn tối đa hóa tổng cấp độ của tất cả các con côn trùng trên sân bằng cách loại bỏ một số con côn trùng. Tổng cấp độ là tổng các cấp độ của từng con côn trùng riêng lẻ. Bạn cần giúp anh ấy tính $ans_K$, tổng cấp độ lớn nhất mà anh ấy có thể đạt được bằng cách loại bỏ tối đa $K$ con côn trùng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$).

Sau đó là $n$ dòng, dòng thứ $i$ chứa hai số nguyên $type_i$ và $level_i$ ($1 \le type_i \le n, 1 \le level_i \le 10^7$).

Dữ liệu ra

In ra $n$ dòng, trong đó dòng thứ $i$ chứa một số nguyên $ans_i$.

Ví dụ

Dữ liệu vào 1

4
1 5
1 6
2 2
3 1

Dữ liệu ra 1

15
20
24
24

Dữ liệu vào 2

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

Dữ liệu ra 2

20
24
27
29
30
30

Dữ liệu vào 3

4
1 1
2 2
3 3
4 4

Dữ liệu ra 3

10
10
10
10