Американские горки

Анна работает в парке развлечений и занимается проектированием нового аттракциона "Американские горки". Аттракцион представляет собой трассу, по которой будет ездить специальный поезд. Будем считать, что поезд имеет нулевую длину. Анна уже спроектировала $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)$.

Выходные данные

Вывести минимальную возможную суммарную длину всех соединительных путей между специальными секциями.

Примеры