MPILOT - Pilots

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mpilot


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 



Được gửi lên bởi:psetter
Ngày:2009-04-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COI 04

hide comments
2021-05-27 18:02:00
Tham khảo: https://vnspoj.github.io/problems/MPILOT
2021-04-15 18:25:55
qhđ hay uwu :))
2020-07-25 13:16:46
TranTrungKienGoldIOI2021
2019-10-19 12:50:27
http://eunsetee.com/Y5An
2019-08-25 12:25:00
heap cơ bản nhé anh em . code : https://ideone.com/4jA4OG
2019-08-02 07:30:29
Có một trợ lí có thể có lương cao hơn đội trưởng nha đề bên này dịch thiếu -_-
2019-06-04 16:04:50
cho mình hỏi ở test case 2, đề ghi rõ là phi công chính lớn tuổi hơn trợ lý, nếu đúng thì mình thử thấp nhất là 34000, còn nếu bỏ điều kiện đó đi thì mình mới ra 32000, liệu có sai đề không mọi người
2019-01-25 16:49:02
Cảm ơn code mẫu ở dưới nhiều ạ
2018-06-29 10:47:45
Xem công thức qhđ và code:
https://vietcodes.github.io/code/145/
2018-02-12 14:24:58 Sơn Tùng M-TP
Quy hoạch động như bài C11KM cũng được nè. Mà mỗi tội tốn hơi nhiều bộ nhớ.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.