Cards

Time limit1sMemory limit128 MB

Summary

Given N double-sided cards, choose an order, a flip for each, and assign alternating plus/minus signs to minimize the resulting alternating sum.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math
Solved: No attempts yet

Problem

Adam loves numbers. One day he found a stack of blank cards in his drawer, wrote one number on each of the two sides of every card, and came up with the following puzzle.

He lays all the cards in a row in any order he likes, and may turn any card over so that its other side faces up. Reading the up-facing numbers from left to right, call them $c_1, c_2, \ldots, c_N$ . Adam then evaluates the alternating sum

$c_1 - c_2 + c_3 - c_4 + \cdots + c_{N-1} - c_N.$

Because the number of cards $N$ is even, the plus and minus signs split exactly in half. Adam wants to make this value as small as possible. Write a program that finds the smallest value he can obtain.

Input

The first line contains the number of cards $N$ ( $2 \le N \le 100\,000$ , and $N$ is even). Each of the next $N$ lines contains two integers $a_i$ and $b_i$ ( $-2000 \le a_i, b_i \le 2000$ ), the numbers written on the two sides of the $i$ -th card.

Output

Print a single integer: the smallest value of the alternating sum that can be obtained by ordering and flipping the cards.

Examples4

Example 1
Input
```
6
-8 12
0 5
7 -3
10 -7
-2 7
1 4
```
Expected output
```
-34
```

Example 2

Input

Expected output

-155

Example 3
Input
```
2
1 2
3 4
```
Expected output
```
-3
```
Example 4
Input
```
4
0 0
0 0
0 0
0 0
```
Expected output
```
0
```