Фермер Джон получил груз из \(N\) больших стогов сена
(\(1 \le N \le 100,000\)), и разместил стога в различных позициях вдоль дороги, соединяющей амбар с его домом. Каждый стог с номером \(j\) имеет размер \(S_j\) и находится в уникальной позиции \(P_j\) определяющей его положение вдоль одномерной дороги. Корова Беси расположена в настоящий момент в позиции \(B\),где нет стога сена.
Беси может передвигаться вдоль дороги вплоть до позиции, где расположен стог сена, но она не может проходить эту позицию. Как исключение, если она движется в некотором направлении \(D\) единиц расстояния, то она набирает скорость достаточную чтобы уничтожить любой стог сена с размером строго меньше, чем \(D\). Конечно после того как она сделает это, она может бежать дальше к другим стогам и уничтожать их аналогичным способом.
ФД перекрасил дои и амбар и хочет быть уверенным, что Беси не доберётся ни туда, ни туда (Корова и свежая краска не есть хорошая комбинация!). Соответственно, ФД хочет быть уверенным, что Беси никогда не выйдет ни за самый левый, ни за самый правый стог. ФД может добавить сена в один стог по своему выбору, так чтобы гарантировать, что Беси не выберется. Пожалуйста, помогите ему определить минимальное количество дополнительного размера, который он должен добавить к некоторому стогу сена, чтобы гарантировать, что Беси останется в ловушке.
ФОРМАТ ВВОДА (файл trapped.in):
Первая строка ввода содержит \(N\) и начальную позицию Беси \(B\).
Каждая из последующих \(N\) строк описывает стог и содержит два целых числа, определяющих его размер и местоположение. Все размеры и положения находятся в диапазоне \(1\ldots 10^9\).
ФОРМАТ ВЫВОДА (файл trapped.out):
Выведите одно целое число, определяющее минимальное количество сена, которое должен добавить ФД чтобы Беси не выбралась из ловушки. Выведите -1, если это сделать невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7
8 1
1 4
3 8
12 15
20 20
|
4
|