Có \(N\) chiếc áo, chiếc áo thứ \(i\) có màu \(F_i\) (ký hiệu bằng một số nguyên từ \(1\) đến \(N\)) và độ thẩm mỹ là \(S_i\). Bạn cần viết chương trình chọn ra một cặp áo có độ tương hợp lớn nhất có thể đối với thầy Như. Biết rằng với một cặp áo gồm hai chiếc áo có độ thẩm mỹ lần lượt là \(s\) và \(t\) \((s\ge t)\), thầy Như định nghĩa độ tương hợp của chúng như sau:

• Nếu hai chiếc áo khác màu sắc, độ tương hợp của cặp áo sẽ bằng \(s+t\).
• Nếu hai chiếc áo có cùng màu sắc, độ tương hợp của cặp áo sẽ bằng \(s+\dfrac{t}{2}\). Dữ liệu đảm bảo \(s\) và \(t\) luôn là hai số nguyên dương chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \(\left(2\le N\le 3\times 10^5\right)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên dương \(F_i\) và \(S_i\) \(\left(1\le F_i\le N, 2\le S_i\le 10^9\right)\). Dữ liệu đảm bảo \(S_i\) luôn là một số nguyên dương chẵn.

Output

• In ra độ tương hợp lớn nhất có thể của một cặp áo mà bạn chọn được.

Ví dụ

Sample input 01

4
4 10
3 2
2 4
4 12

Sample output 01

17

Giải thích

Chọn hai chiếc áo có cùng màu số \(4\), ta được độ tương hợp là \(12+\dfrac{10}{2}=17\).

Sample input 02

4
1 4
2 10
2 8
3 6

Sample output 02

16

Giải thích

Chọn hai chiếc áo có độ thẩm mỹ lần lượt là \(10\) và \(6\), ta được độ tương hợp là \(10+6=16\) (vì hai chiếc áo này không trùng màu).