Телепортация (Серебро)
Большего всего из фермерских забот Фермер Джон ненавидит убирать лотки с коровьим навозом. Для того чтобы упростить процесс он придумал телепортер навоза. Вместо того, чтобы везти навоз в тележке за трактором, он может использовать телепортер для перемещения навоза из одного места в другое.
Ферма Джона построена вдоль длинной прямой дороги, поэтому любое место фермы может быть описано его позицией на этой дороге (точка на числовой прямой). Телепорт описывается двумя числами x и y, которые обозначают, что навоз из точки x может быть мгновенно телепортирован в точку y.
ФД решил построить телепорт с первой конечной точкой расположенной в x = 0. Ваша задача помочь ему определить наилучший выбор для другой конечной точки y. В частности, имеется n (1 ≤ n ≤ 10^5) лотков с навозом на ферме. i-ый лоток нужно переместить с позиции a[i] в позицию b[i] и ФД транспортирует каждый лоток отдельно от других. Обозначим d[i] расстояние,на которое нужно перевезти каждый лоток. d[i] может быть потенциально меньше, если ФД использует телепорт (везя на тракторе от a[i] до x и затем от y до b[i]).
Помогите ФД определить минимально возможную сумму d[i] которую может достичь ФД, правильно выбрав значение y (второго конца телепорта). Одно и то же значение y используется для транспортировки всех лотков.
Входные данные
Первая строка ввода содержит число n. Каждая из последующих n строк содержит по два целых числа a[i] и b[i], в интервале -10^8...10^8. Все значения не обязательно различны.
Выходные данные
Выведите одно число - минимальную сумму d[i], которую может достичь ФД. Заметим, что это число может превысить 32-битное целое, поэтому нужно использовать больший тип данных, например "long long" в C/C++.
Пример
В этом примере установив y = 8 ФД может получить d[1] = 2, d[2] = 5, d[3] = 3. Заметим, что любое значение y в интервале [7, 10] также поддерживает оптимальное решение.