Nhân ngày sinh nhật, hai anh em sinh đôi Téo và Tỳ nhận được N món quà, N là một số chẵn. Mỗi người gán cho mỗi món quà một giá trị ưa thích – là một số nguyên dương nhỏ hơn 100 . Giá trị này thể hiện mức độ hạnh phúc họ có được nếu có được món quà đó. Sau đó, 2 anh em quyết định chia quà, hai người có số lượng quà bằng nhau và bằng N/2. Hãy xác định cách chia quà sao cho tổng mức độ hạnh phúc của hai anh em là lớn nhất.

Dữ liệu vào:

Dòng đầu là số nguyên dương N<=500000.

N dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương a và b <=100 là giá trị ưa thích của 2 người với từng món quà.

Dữ liệu ra:

Tổng mức độ hạnh phúc cực đại.

Sample Input

4
1 2
2 3
3 5
2 1

Sample Output

11