MPILOT - Pilots
Giới hạn- Thời gian: 0.656s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Charlie sở hữu vài cái máy bay bà già và cần tối ưu chi phi để 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 1 hợp đồng thì lương lái chính > 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.
Input
Dòng đầu là N (N chẵn), số phi công, 2 ≤ N ≤ 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 ≤ Y < X ≤ 100,000.
Các phi công sắp tăng dần theo tuổi.
Output
Lương nhỏ nhất cần trả.
Sample
input 4 5000 3000 6000 2000 8000 1000 9000 6000 output 19000 input 6 10000 7000 9000 3000 6000 4000 5000 1000 9000 3000 8000 6000 output 32000
- Người up: vdmedragon
- Nguồn bài: COI 04