Анна работает в парке развлечений и занимается проектированием нового аттракциона "Американские горки". Аттракцион представляет собой трассу, по которой будет ездить специальный поезд. Будем считать, что поезд имеет нулевую длину. Анна уже спроектировала n специальных секций (удобно пронумерованных от 0 до n−1), которые влияют на скорость поезда: подъёмы, резкие торможения, и т. д. Теперь она должна соединить их путями, чтобы получить окончательный план аттракциона.
Для каждого i от 0 до n−1, включительно, специальная секция i характеризуется двумя значениями:
при въезде на эту секцию есть ограничение скорости: скорость поезда при въезде на секцию должна быть меньше или равна si км/ч,
при выезде с секции, скорость поезда становится равна в точности ti км/ч, вне зависимости от скорости, с которой поезд въехал на секцию.
В итоге план аттракциона должен представлять собой единую трассу, на которой в некотором порядке встречаются все n специальных секций. Каждая из n секций должна войти в окончательный план аттракциона ровно один раз.
Между последовательными секциями должны быть проложены соединительные пути. Анна должна решить, в каком порядке расположить секции в вдоль трассы аттракциона, и выбрать длину каждого из соединительных путей. Длина каждого соединительного пути измеряется в метрах и должна представлять собой неотрицательное целое число (возможно равное нулю).
Каждый метр соединительного пути между двумя специальными секциями замедляет поезд на 1 км/ч. В начале поездки поезд въезжает на первую специальную секцию на трассе со скоростью 1 км/ч.
Окончательный план аттракциона должны отвечать следующим требованиям:
поезд не нарушает ограничения на скорость въезда на специальные секции;
скорость поезда должна быть строго положительной в любой момент движения по трассе.
Вам требуется выбрать порядок специальных секций и длины соединительных путей между ними так, чтобы приведенные требования выполнялись, и суммарная длина соединительных путей была как можно меньше.
Первая строка содержит число n (2≤n≤2⋅105). Каждая из следующих n строк содержит числа si и ti (1≤i≤n,1≤si,ti≤109).
Вывести минимальную возможную суммарную длину всех соединительных путей между специальными секциями.