Американські гірки

Анна працює в парку розваг і займається проектуванням нового атракціону "Американські гірки". Атракціон складається з траси, по якій буде їздити спеціальний поїзд. Вважатимемо, що поїзд має нульову довжину. Анна вже спроектувала $n$ спеціальних секцій (зручно пронумерованих від $0$ до $n-1$), які впливають на швидкість поїзда: підйоми, різкі гальмування тощо. Тепер вона повинна з'єднати їх шляхами, щоб отримати остаточний план атракціону.

Для кожного $i$ від $0$ до $n-1$, включно, спеціальна секція $i$ характеризується двома значеннями:

• при в'їзді на цю секцію є обмеження швидкості: швидкість поїзда при в'їзді на секцію повинна бути меншою або дорівнювати $s_i$ км/год,

• при виїзді з секції, швидкість поїзда стає рівно $t_i$ км/год, незалежно від швидкості, з якою поїзд в'їхав на секцію.

В результаті план атракціону повинен являти собою єдину трасу, на якій у певному порядку зустрічаються всі $n$ спеціальних секцій. Кожна з $n$ секцій повинна увійти в остаточний план атракціону рівно один раз.

Між послідовними секціями повинні бути прокладені з'єднувальні шляхи. Анна повинна вирішити, в якому порядку розташувати секції вздовж траси атракціону, і вибрати довжину кожного з'єднувального шляху. Довжина кожного з'єднувального шляху вимірюється в метрах і повинна являти собою невід'ємне ціле число (можливо рівне нулю).

Кожен метр з'єднувального шляху між двома спеціальними секціями уповільнює поїзд на $1$ км/год. На початку поїздки поїзд в'їжджає на першу спеціальну секцію на трасі зі швидкістю $1$ км/год.

Остаточний план атракціону повинен відповідати наступним вимогам:

• поїзд не порушує обмеження на швидкість в'їзду на спеціальні секції;

• швидкість поїзда повинна бути строго позитивною в будь-який момент руху по трасі.

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

Вхідні дані

Перша рядок містить число $n(2\le n\le 2\cdot 10^5)$. Кожен з наступних $n$ рядків містить числа $s_i$ і $t_i(1\le i\le n,1\le s_i,t_i\le 10^9)$.

Вихідні дані

Вивести мінімальну можливу сумарну довжину всіх з'єднувальних шляхів між спеціальними секціями.

Приклади