MPILOT - Pilots





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 

hide comments
anubhav448: 2025-04-13 11:11:56

Problem statement:
N pilots array is given with each pilot can be Captain as well as Assistant and their salaries are given.
We need to created N/2 crews out of N pilots such that each crew has 2 pilots, 1 has a role of Cap and other has a role of Assistant, constraint is age(Ass.) < age(Cap). Find min salary.

" A captain's salary is larger than assistant's for the same pilot. However, it is possible that an assistant has larger salary than his captain " ---> means that : For same pilot, Salary(as a captain) > Salary(as an Ass.). But in a crew formed, Salary(of a pilot 1 as a Cap. ) < Salary(of a pilot 2 as a Ass.). Hope it helps!

arpitsingh9631: 2024-11-05 19:26:18

first of all i didn't understand the problem ?

lamvu45: 2023-11-23 05:30:02

ko vui dau bn

giavu: 2023-11-23 05:29:37

@lamvu45 may ngu

lamvu45: 2023-11-23 05:29:13

mmb


Added by:psetter
Date:2009-04-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 04