MPILOT  Pilots
English  Vietnamese 
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
little_finger:
20190630 08:10:27
If you are getting runtime error, try creating static dp array  int dp[5001][5001]. It worked for me. 

samster:
20190407 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:
20181229 18:09:08
same logic accepted in c++ but giving TLE in java plz it is happening in many questions someone hhelp:)


ihg_2_26:
20180911 16:36:04
recursion+memorization gives wa.. Anybody help?


soham_12345:
20180616 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:
20180614 10:08:03
Nice Question! Be careful about size of dp array. 

shivamgarg1901:
20180523 14:03:40
Compare it with the problem of printing all the valid parenthesis.


arindam1234:
20170813 14:02:02
my 150th question!!! 

mkfeuhrer:
20170529 22:22:29
my 300th :D , although took help from comments!! O(n^2) 

escalibor_4o:
20170128 17:25:44
must for dp beginners!!!!

Added by:  ~!(*(@*!@^& 
Date:  20090425 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COI 04 