B. Сила мысли
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Магистр-джедай Йода способен передвигать предметы силой мысли. Его сила мысли измеряется в интеллах. Чтобы сдвинуть, например, камень массой $$$3$$$ кг на $$$5$$$ метров, ему нужно потратить $$$3 \times 5=15$$$ интеллов силы.

В начальный момент времени все камни находятся по одну сторону от воображаемой прямой линии $$$L$$$, причём каждый камень располагается на заданном целом расстоянии от этой линии (некоторые камни могут даже лежать на $$$L$$$, т.е. находиться на расстоянии $$$0$$$ от неё). Йода хочет добиться максимального результата, используя имеющуюся у него силу. Он хочет так отодвинуть камни на целое число метров от прямой $$$L$$$, чтобы после сдвига ближайший к $$$L$$$ камень оказался как можно дальше от неё.

Требуется выяснить, на каком максимальном расстоянии от линии $$$L$$$ может оказаться ближайший к ней камень после сдвига, если Йода обладает силой заданной величины?

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

В первой строке записаны два числа $$$N$$$ и $$$F$$$ — число камней и величина силы в интеллах $$$(1 \le N \le 10^5,1 \le F \le 10^{15})$$$.

В последующих $$$N$$$ строках записаны через пробел по два целых числа $$$m_i$$$ и $$$d_i$$$ — масса $$$i$$$-го камня и расстояние от него до линии $$$L$$$ $$$(1 \le m_i \le 10^3, 0 \le d_i \le 10^5)$$$.

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

Выведите одно целое неотрицательное число — искомое максимальное расстояние от линии $$$L$$$ до ближайшего к ней камня после сдвига.

Система оценки

Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.

ПодгруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$0$$$Тест из условия$$$0$$$—
$$$1$$$$$$N \le 10,\ F \le 20$$$$$$15$$$$$$0$$$
$$$2$$$$$$N \le 10$$$$$$20$$$$$$0,\ 1$$$
$$$3$$$$$$N \le 10^4$$$$$$25$$$$$$0$$$ – $$$2$$$
$$$4$$$—$$$40$$$$$$0$$$ – $$$3$$$
Пример
Входные данные
4 25
3 2
2 0
5 2
1 1
Выходные данные
3
Примечание

В примере у Йоды есть $$$25$$$ интеллов силы. Он может, например, сдвинуть камень массой $$$3$$$ кг на 2 метра, камень массой $$$2$$$ кг на $$$5$$$ метров, камень массой $$$5$$$ кг на $$$1$$$ метр, камень массой $$$1$$$ кг на $$$4$$$ метра.

В итоге ближе всего к линии $$$L$$$ окажется камень массой 5 кг. Он будет находиться от неё на расстоянии $$$3$$$ метра. Возможны и другие варианты сдвигов, но в любом случае после сдвига ближайший к линии $$$L$$$ камень будет находиться не дальше, чем в $$$3$$$ метрах от неё.