시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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.

예제 입력 1

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

예제 출력 1

-34

Cards are put to the expression in this order: 1st, 2nd, 3rd, 5th, 4th, 6th.

(-8) - 5 + (-3) - 7 + (-7) - 4 = -34

예제 입력 2

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

예제 출력 2

-155

Cards are put to the expression in this order: 2nd, 1st, 4th, 3rd, 5th, 8th, 6th, 9th, 7th, 10th.

62 - 70 + 59 - 81 + 40 – 76 + 35 – 85 + 57 - 96 = -155