Câu 4 đề HSG L9 Yên Thành

Để kết thúc buổi sinh hoạt lớp lập trình, thầy giáo bộ môn đã chuẩn bị ~N~ (~1≤N≤500000~, ~N~ chẵn) phần quà cho hai tổ. Mỗi tổ gán một giá trị ưu thích (là một số nguyên dương ~≤100~) mà mình nghĩ vào phần quà. Sau đó, thầy giáo cho mỗi tổ nhận ~N/2~ phần quà sao cho tổng giá trị ưu thích của hai tổ lớn nhất.

Yêu cầu:

Bạn hãy giúp thầy giáo tìm tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.

Dữ liệu:

• Dòng 1 chứa số nguyên dương chẵn ~N~
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~ là giá trị tổ 1 và 2 gán cho món quà thứ ~i~.

  Kết quả:

Một số nguyên duy nhất là tổng số giá trị ưa thích lớn nhất sau khi mỗi tổ đã chọn ~N/2~ phần quà.

Ví dụ

Input

4
1 2
2 3
3 5
2 1

Output

11

Giải thích

• Tổ 1 chọn phần quà thứ 1 và thứ 4
• Tổ 2 chọn phần quà thứ 2 và thứ 3