MPILOT - Pilots


Charlie acquired airline transport company and to stay in business he needs to lower the expenses by any means possible. There are N pilots working for his company (N is even) and N/2 plane crews needs to be made. A plane crew consists of two pilots - a captain and his assistant. A captain must be older than his assistant. Each pilot has a contract granting him two possible salaries - one as a captain and the other as an assistant. 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. Write a program that will compute the minimal amount of money Charlie needs to give for the pilots' salaries if he decides to spend some time to make the optimal (i.e. the cheapest) arrangement of pilots in crews.

Input

The first line of input contains integer N, 2 ≤ N ≤ 10,000, N is even, the number of pilots working for the Charlie's company. The next N lines of input contain pilots' salaries. The lines are sorted by pilot's age, the salaries of the youngest pilot are given the first. Each of those N lines contains two integers separated by a space character, X i Y, 1 ≤ Y < X ≤ 100,000, a salary as a captain (X) and a salary as an assistant (Y).

Output

The first and only line of output should contain the minimal amount of money Charlie needs to give for the pilots' salaries.

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
samster: 2019-04-07 21:29:58

getting runtime error....what might be the problem...used recursion+memorization....however always goes to last test case and gives runtime.

rahul_107: 2018-12-29 18:09:08

same logic accepted in c++ but giving TLE in java plz it is happening in many questions someone hhelp:)
contact me sachinlather49@gmail.com

ihg_2_26: 2018-09-11 16:36:04

recursion+memorization gives wa.. Anybody help?

Last edit: 2018-09-21 07:54:23
soham_12345: 2018-06-16 06:33:27

Why are people complaining about N^2 passing? Isn't it obvious to pass? And complexity is N^2/2 not N^2 which makes 5e7 operations. Anyways I was wondering if there is a O(N) soln

na0013: 2018-06-14 10:08:03

Nice Question! Be careful about size of dp array.

shivamgarg1901: 2018-05-23 14:03:40

Compare it with the problem of printing all the valid parenthesis.
Happy Coding!

Last edit: 2018-05-23 14:06:38
arindam1234: 2017-08-13 14:02:02

my 150th question!!!

mkfeuhrer: 2017-05-29 22:22:29

my 300th :-D , although took help from comments!! O(n^2)

escalibor_4o: 2017-01-28 17:25:44

must for dp beginners!!!!

devbishnoi: 2016-10-21 19:05:36

Ac in one go ... O(n^2) works
tips : make array of dp[5001][5001] size for memorisation
do not think of long long
because max value of ans (10000*100000) will not exceed int size

Last edit: 2016-10-21 19:09:25

Added by:~!(*(@*!@^&
Date:2009-04-25
Time limit:0.432s-0.656s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 04