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.
Input
The first line contains the number of cards N (2 ≤ N ≤ 100000, N is an even integer). Each of the following N lines contains two integers a_i and b_i (-2000 ≤ a_i, b_i ≤ 2000; i = 1..N). These are the numbers written on separate sides of the i-th card.
Output
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.
Comment
1: 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
2: 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