Задачи
Американские горки
Американские горки
Анна работает в парке развлечений и занимается проектированием нового аттракциона "Американские горки". Аттракцион представляет собой трассу, по которой будет ездить специальный поезд. Будем считать, что поезд имеет нулевую длину. Анна уже спроектировала $n$ специальных секций (удобно пронумерованных от $0$ до $n - 1$), которые влияют на скорость поезда: подъёмы, резкие торможения, и т. д. Теперь она должна соединить их путями, чтобы получить окончательный план аттракциона.
Для каждого $i$ от $0$ до $n - 1$, включительно, специальная секция $i$ характеризуется двумя значениями:
\begin{itemize}
\item при въезде на эту секцию есть ограничение скорости: скорость поезда при въезде на секцию должна быть меньше или равна $s_i$ км/ч,
\item при выезде с секции, скорость поезда становится равна в точности $t_i$ км/ч, вне зависимости от скорости, с которой поезд въехал на секцию.
\end{itemize}
В итоге план аттракциона должен представлять собой единую трассу, на которой в некотором порядке встречаются все $n$ специальных секций. Каждая из $n$ секций должна войти в окончательный план аттракциона ровно один раз.
Между последовательными секциями должны быть проложены соединительные пути. Анна должна решить, в каком порядке расположить секции в вдоль трассы аттракциона, и выбрать длину каждого из соединительных путей. Длина каждого соединительного пути измеряется в метрах и должна представлять собой неотрицательное целое число (возможно равное нулю).
Каждый метр соединительного пути между двумя специальными секциями замедляет поезд на $1$ км/ч. В начале поездки поезд въезжает на первую специальную секцию на трассе со скоростью $1$ км/ч.
Окончательный план аттракциона должны отвечать следующим требованиям:
\begin{itemize}
\item поезд не нарушает ограничения на скорость въезда на специальные секции;
\item скорость поезда должна быть строго положительной в любой момент движения по трассе.
\end{itemize}
Вам требуется выбрать порядок специальных секций и длины соединительных путей между ними так, чтобы приведенные требования выполнялись, и суммарная длина соединительных путей была как можно меньше.
\InputFile
Первая строка содержит число $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)$.
\OutputFile
Вывести минимальную возможную суммарную длину всех соединительных путей между специальными секциями.
Входные данные #1
4 1 7 4 3 5 8 6 6
Выходные данные #1
3
Входные данные #2
2 753393670 164885444 893746473 737884286
Выходные данные #2
0