Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Charlie sở hữu vài cái máy bay bà già và cần tối ưu chi phí để kiếm lời.

Có ~N~ phi công (~N~ chẵn) và cần có ~N/2~ phi hành đoàn. Mỗi phi hành đoàn gồm 2 người – 1 lái chính, 1 trợ lí. Lái chính phải cao tuổi hơn trợ lí. Hợp đồng cho mỗi phi công có ghi mức lương nếu anh ta là lái chính hoặc là trợ lí. Với mỗi hợp đồng thì lương lái chính lớn hơn lương trợ lí.

Tìm cách ghép cặp sao cho tổng lương phải trả cho ~N~ người là ít nhất.

Dữ liệu vào

• Dòng đầu là ~N~ (~N~ chẵn), số phi công, ~2 \le N \le 10\,000~.
• ~N~ dòng tiếp theo, mỗi dòng là 2 số ~X~, ~Y~ là lương phi công thứ ~i~ nếu làm lái chính hoặc trợ lí, ~1 \le Y \lt X \le 100\,000~. Các phi công sắp tăng dần theo tuổi.

Kết quả

• Lương nhỏ nhất cần trả.

Sample Input 1

4
5000 3000
6000 2000
8000 1000
9000 6000

Sample Output 1

19000

Sample Input 2

6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000

Sample Output 2

32000

Nguồn: VNOJ (MPILOT).