Nguồn

Nhân ngày sinh nhật, hai anh em sinh đôi Tý và Tèo nhận được 2*N món quà. Mỗi người có một mức độ yêu thích khác nhau đối với mỗi món quà.

Yêu cầu: Hãy tìm cách chia quà để mỗi người nhận được đúng N món quà và tổng mức độ yêu thích của 2 anh em đối với các món quà được chia là lớn nhất.

Dữ liệu vào:

• Dòng đầu là số nguyên dương N ≤ 10^5;
• 2*N dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương a và b tương ứng là mức độ yêu thích của Tý và Tèo với từng món quà. (a, b ≤ 1000)

Kết quả:

Ghi ra một số là tổng mức độ yêu thích lớn nhất của hai anh em.

Ví dụ:

Input

2
2 1
3 5
2 3
1 2

Output

11

Giải thích VD

Một cách chia là: chia cho Tý món quà 1 và 3 (được tổng 2+2=4); Tèo nhận món quà 2 và 4 (được tổng 5+2=7).

Nguồn