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 ~\frac{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.

Input

• 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à.

Output

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

Sample

Input #1

4
1 2
2 3
3 5
2 1

Output #1

11

Problem source: Đề đề xuất PreVNOI 2013 của Trường KHTN