Để 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: vào từ file THUONG.INP có cấu trúc:

• 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 ai và bi là giá trị tổ 1 và 2 gán cho món quà thứ i.

Kết quả: ghi file THUONG.OUT 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ụ