프로그램 명: boi_cards
제한시간: 1 초

N개의 카드 양면에 각각 숫자를 대입합니다.

카드가 a와 b면으로 되어있을때

순서에 상관없이 카드 a or b면의 숫자 + 카드 a or b면의 숫자 - 카드 a or b면의 숫자 + 카드 a or b면의 숫자.... (덧셈뺄셈 반복입니다. 카드에 적혀있는 숫자 2개중 하나만 사용합니다.)

위 공식대로 카드들의 숫자를 대입할 경우 나올 수 있는 가장 최소값을 구하는 문제입니다.

입력

출력

문제의 공식에 카드들의 숫자를 대입할 경우 가장 최소값이 나올 경우를 출력합니다.

입출력 예 - 상세설명 

입력 

6 (총 6개의 카드를 사용합니다.) 
-8 12  (첫번째 카드에 적혀있는 숫자를 의미합니다. a1=-8, b1=12) 
0 5  
7 -3  
10 -7  
-2 7  
1 4  

출력 

-34   

Cards are put to the expression in this order: 1 st , 2 nd , 3 rd , 5 th , 4 th , 6 th .   
(-8) - 5 + (-3) - 7 + (-7) - 4 = -34 


출력값이 상당히 복잡합니다 -_-;  

첫번째 숫자는 공식에 대입한 후 나온 최소값입니다.  

두번째줄은 보이는 영문자를 다 쓴 후 몇번째 카드를 공식에 사용했는지 순서대로 적는 란입니다.(영어에서는 서수를 입력할땐 1,2,3의 경우를 제외하고 모든 숫자에 th를 붙이면 됩니다.) 

세번째는 실제로 대입한 값을 출력해 보이라는 의미입니다. 각각 a면이나 b면중 골라서 하나를 썼습니다.  
무슨 면의 숫자를 사용했는지는 쓰지 않습니다. 보기와 같이 값이 -이면 괄호를 무조건 붙여줘야 됩니다. 

입력 

10  
70 70  
62 73  
81 65  
59 77  
99 40  
35 88  
80 57  
76 67  
85 57  
53 96  

출력 

-155   

Cards are put to the expression in this order: 2 nd , 1 st , 4 th , 3 rd , 5 th , 8 th , 6 th , 9 th , 7 th , 10 th .  
 62 - 70 + 59 - 81 + 40 ? 76 + 35 -  85 + 57 - 96 = -155
Adam has a fancy for numbers. Once he found a batch of empty paper cards in his drawer, wrote random numbers on both sides of each card and thought of the following puzzle: what smallest possible value can be obtained by putting all cards in an arbitrary order (and upturned if necessary) to the expression of the following form: □ ® - ® + ® - ® + ® - ® + ... - ® After a while Adam came up with a solution. Could you do that too? Write a program to solve the puzzle described above.

입력

The first line contains the number of cards N (2 ￡ N ￡ 100 000, N is an even integer). Each of the following N lines contains two integers ai and bi (-2000 ≤ ai, bi ≤ 2000; i = 1…N). These are the numbers written on separate sides of the i-th card.

출력

The first and the only line should contain the minimal value that can be obtained by putting all the cards to the expression as described above.

입출력 예

입력

6 
-8 12 
0 5 
7 -3 
10 -7 
-2 7 
1 4 

출력

-34  

Cards are put to the expression in this order: 1 st , 2 nd , 3 rd , 5 th , 4 th , 6 th .  
(-8) - 5 + (-3) - 7 + (-7) - 4 = -34

입력

10 
70 70 
62 73 
81 65 
59 77 
99 40 
35 88 
80 57 
76 67 
85 57 
53 96 

출력

-155  

Cards are put to the expression in this order: 2 nd , 1 st , 4 th , 3 rd , 5 th , 8 th , 6 th , 9 th , 7 th , 10 th . 
 62 - 70 + 59 - 81 + 40 ? 76 + 35 -  85 + 57 - 96 = -155 

출처:boi 2005 practice
번역:ironamor
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]