eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Картки

Картки

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Адам любить фантазувати з числами. Одного разу він у коробці знайшов пачку чистих картоних карток, написав з обох сторон якесь випадкове число і почав думати над наступною ломиголовкою: яке найменше значення можна отримати, якщо підставити карти у довільному порядку (при необхідності їх можна перевертати) у наступний вираз:

Через деякий час Адам придумав розв'язок. А Ви зможете це зробити? Напишіть програму, яка розв'язує ломиголовку, описану вище.

Вхідні дані

Перший рядок містить єдине натуральне число - кількість карток N (2N100000, N парне число). Кожен з наступних N рядків містить два цілих числа a_i та b_i (-2000a_i, b_i2000; i = 1..N). Це числа, записані на кожній зі сторін i-ї картки.

Вихідні дані

Перший і єдиний рядок повинен містити мінімальне значення, яке можна отримати підставивши усі картки у вираз, описаний вище.

Примітка

1: Картки потрібно розмістити у такому порядку: 1^st, 2^nd, 3^rd, 5^th, 4^th, 6^th.

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

2: Картки потрібно розмістити у такому порядку: 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

Приклад

Вхідні дані #1
6
-8 12
0 5
7 -3
10 -7
-2 7
1 4
Вихідні дані #1
-34
Джерело BOI-2005