Телепортація (Срібло)
Фермер Джон найбільше не любить прибирати лотки з коров'ячим гноєм. Щоб полегшити цю роботу, він винайшов телепортер для гною. Замість того, щоб перевозити гній у візку за трактором, він може використовувати телепортер для переміщення гною з одного місця в інше.
Ферма Джона розташована вздовж довгої прямої дороги, тому будь-яке місце на фермі можна описати його позицією на цій дорозі (точка на числовій прямій). Телепорт описується двома числами 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] також забезпечує оптимальне рішення.