Description

Adam likes numbers. Once, he found a stack of blank paper cards in his drawer. He wrote random numbers on both sides of each card, and then thought about the following puzzle: put all cards into the expression of the following form in any order (flipping them if necessary). What is the minimum possible value of the resulting expression?

□-□+□-□+□-□+...-□ (both the first operator and the last operator are -)

After a while, Adam came up with a solution. Can you do it too? Write a program to solve the puzzle described above.

Input Format

The first line of standard input contains the number of cards $N$.

In the next $N$ lines, the $(i+1)$-th line contains two integers $a_i$ and $b_i$, which are the numbers written on the two sides of the $i$-th card.

Output Format

Standard output contains only one line, which should contain the minimum possible value of the expression.

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

-34

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

-155

Hint

Explanation for Sample 1

The order of cards placed into the expression is: $1,2,3,5,4,6$.

Then the minimum value is $(-8) - 5 + (-3) - 7 + (-7) - 4 = -34$.

Explanation for Sample 2

The order of cards placed into the expression is: $2,1,4,3,5,8,6,9,7,10$.

Then the minimum value is $62 - 70 + 59 - 81 + 40 - 76 + 35 - 85 + 57 - 96 = -155$.

Constraints

For $100\%$ of the testdata, $2 \le N \le 10^5$, $N$ is even (for obvious reasons), and $|a_i|, |b_i| \le 2000$.

Notes

Translated from BalticOI 2005 Day0 Card.

The original official website for this problem has been lost. The original testdata can be judged here.

Translated by ChatGPT 5