Телепортація (Срібло)#10410

Телепортація (Срібло)

1 секунда

128 мегабайтів

Складна

Одна з фермерських справ, яку фермер Джон не любить найбільше, — це перевезення великих обсягів коров'ячого гною. Щоб спростити цей процес, він придумав геніальний винахід: телепортер для гною! Замість того, щоб возити гній між двома точками у візку за своїм трактором, він може скористатися телепортером для гною, щоб миттєво перемістити гній з одного місця в інше.

Ферма фермера Джона розташована вздовж однієї довгої прямої дороги, тому будь-яке місце на фермі можна описати просто його позицією вздовж цієї дороги (фактично, точкою на числовій прямій). Телепортер описується двома числами $x$ та $y$ : гній, привезений у позицію $x$ , може бути миттєво перенесений у позицію $y$ .

Фермер Джон вирішив побудувати телепортер, перший кінець якого знаходиться в точці $x = 0$ x = 0. Ваше завдання — допомогти йому вибрати найкращу позицію для іншого кінця $y$ . А саме, на його фермі є $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) куп гною. $i$ -ту купу потрібно перемістити з позиції $a_{i}$ a_i у позицію $b_{i}$ b_i, і фермер Джон перевозить кожну купу окремо. Нехай $d_{i}$ d_i позначає відстань, яку фермер Джон проїжджає на тракторі з гноєм, перевозячи $i$ -ту купу. Якщо він перевозить $i$ -ту купу безпосередньо трактором, то $d_{i} = ∣ a_{i} - b_{i} ∣$ d_i = |a_i - b_i|; якщо він використовує телепортер (наприклад, везучи купу трактором з $a_{i}$ a_i до $x$ , а потім від $y$ до $b_{i}$ b_i), $d_{i}$ d_i може виявитися меншим.

Допоможіть фермеру Джону визначити мінімально можливу суму значень $d_{i}$ d_i, яку він може досягти, розмістивши інший кінець $y$ телепортера в оптимально обраній позиції. Одна й та сама позиція $y$ використовується для перевезення кожної купи.

Вхідні дані

Перший рядок містить ціле число $n$ . Кожен з наступних $n$ рядків містить два цілих числа $a_{i}$ a_i та $b_{i} (- 1 0^{8} \leq a_{i}, b_{i} \leq 1 0^{8})$ b_i~(-10^8 \le a_i, b_i \le 10^8). Ці значення не обов'язково є різними.

Вихідні дані

Виведіть одне ціле число — мінімальну суму значень $d_{i}$ d_i, яку може досягти фермер Джон. Зауважте, що це число може не вміститися у стандартний 32-бітний цілий тип, тому вам може знадобитися 64-бітний цілий тип, такий як long long у C/C++.

Приклади

У цьому прикладі, встановивши $y = 8$ y = 8, фермер Джон може досягти $d_{1} = 2$ d_1 = 2, $d_{2} = 5$ d_2 = 5 та $d_{3} = 3$ d_3 = 3. Зауважте, що будь-яке значення $y$ у діапазоні $[7, 10]$ також дає оптимальний розв'язок.

Приклад 1