eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Анна работает в парке развлечений и занимается проектированием нового аттракциона "Американские горки". Аттракцион представляет собой трассу, по которой будет ездить специальный поезд. Будем считать, что поезд имеет нулевую длину. Анна уже спроектировала n специальных секций (удобно пронумерованных от 0 до n - 1), которые влияют на скорость поезда: подъёмы, резкие торможения, и т. д. Теперь она должна соединить их путями, чтобы получить окончательный план аттракциона.

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

  • при въезде на эту секцию есть ограничение скорости: скорость поезда при въезде на секцию должна быть меньше или равна s_i км/ч,

  • при выезде с секции, скорость поезда становится равна в точности t_i км/ч, вне зависимости от скорости, с которой поезд въехал на секцию.

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

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

Каждый метр соединительного пути между двумя специальными секциями замедляет поезд на 1 км/ч. В начале поездки поезд въезжает на первую специальную секцию на трассе со скоростью 1 км/ч.

Окончательный план аттракциона должны отвечать следующим требованиям:

  • поезд не нарушает ограничения на скорость въезда на специальные секции;

  • скорость поезда должна быть строго положительной в любой момент движения по трассе.

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

Giriş verilənləri

Первая строка содержит число 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).

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4
1 7
4 3
5 8
6 6
Çıxış verilənləri #1
3
Giriş verilənləri #2
2
753393670 164885444
893746473 737884286
Çıxış verilənləri #2
0
Mənbə 2016 IOI Казань, Россия, День 1