Codah ClubUshtrohu. Dërgo. Përmirësohu.
Hyr
Shqip
#000088

cards

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.


InputThe first line of standard input 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.

OutputFirst line of standard output and the only line should contain the minimal value that can be obtained by putting all the cards to the expression as described above.

Input:
6
-8 12
0 5
7 -3
10 -7
-2 7
1 4
Output:
-34

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


Input:
10
70 70
62 73
81 65
59 77
99 40
35 88
80 57
76 67
85 57
53 96
Output:
-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

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.