Большего всего из фермерских забот Фермер Джон ненавидит убирать лотки с
коровьим навозом. Для того чтобы упростить процесс он придумал телепортер навоза.
Вместо того, чтобы везти навоз в тележке за трактором, он может использовать
телепортер для перемещения навоза из одного места в другое.
Ферма Джона построена вдоль длинной прямой дороги, поэтому любое место фермы
может быть описано его позицией на этой дороге (точка на числовой прямой).
Телепортер описывается двумя числами \(x\) и \(y\), которые обозначают, что навоз из
точки \(x\) может быть мгновенно телепортирован в точку \(y\).
ФД решил построить телепортер с первой конечной точкой расположенной в \(x=0\);
Ваша задача помочь ему определить наилучший выбор для другой конечной точки \(y\).
В частности, имеется \(N\) лотков с навозом на ферме (\(1 \leq N \leq 100,000\)).
\(i\)-ый лоток нужно переместить с позиции \(a_i\) в позицию \(b_i\) и ФД транспортирует
каждый лоток отдельно от других. Обозначим \(d_i\) расстояние,на которое нужно
перевезти каждый лоток. \(d_i\) может быть потенциально меньше, если ФД использует
телепортер (везя на тракторе от \(a_i\) до \(x\) и затем от \(y\) до \(b_i\)).
Пожалуйста, помогите ФД определить минимально возможную сумму \(d_i\) которую
может достичь ФД, правильно выбрав значение \(y\) (второго конца телепорта). Одно
и то же значение \(y\) используется для транспортировки всех лотков.
ФОРМАТ ВВОДА (файл teleport.in):
Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк содержит по
два целых числа \(a_i\) и \(b_i\), в интервале \(-10^8 \ldots 10^8\). Все значения
не обязательно различны.
ФОРМАТ ВЫВОДА (файл teleport.out):
Выведите одно число - минимальную сумму \(d_i\), которую может достичь ФД.
Заметим, что это число может превысить 32-битное целое, поэтому нужно использовать
больший тип данных, например "long long" в C/C++.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
-5 -7
-3 10
-2 7
|
10
|