Phú ông vì rất giàu có nên đã mua một vài máy bay và đầu tư để 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 một hợp đồng thì lương lái chính > lương trợ lí.
Phú ông muốn 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: Cú pháp như sau:
+ Dòng đầu tiên chứa N (2 ≤ N ≤ 104) là số phi công;
+ 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: In ra lương nhỏ nhất cần trả.
Input |
Output |
4 5000 3000 6000 2000 8000 1000 9000 6000 |
19000 |
6 10000 7000 9000 3000 6000 4000 5000 1000 9000 3000 8000 6000 |
32000 |