Задача №112805. Пирожные
Сегодня у Скруджа день рождения!
В подарок он получил целый стол пирожных. Так как у миллионеров не очень много свободного времени, Скрудж хочет съесть как можно больше пирожных за \(T\) секунд.
Стол с пирожными можно представить как бесконечную прямую. Каждое пирожное задается на этой прямой своей координатой \(x_i\). Для того, чтобы перейти от пирожного \(i\) к пирожному \(j\) Скрудж тратит \(|x_i - x_j|\) секунд. Также, для каждого пирожного Скрудж прикинул время \(t_i\) в секундах, за которое он сможет его съесть. Если несколько пирожных располагаются в одной точке, то Скруджу не надо перемещаться от одного у другому, но он может есть их только по очереди.
Изначально Скрудж стоит в точке с координатой \(0\). Помогите Скруджу выяснить какое максимальное количество пирожных он может успеть съесть за время \(T\).
В первой строке входного файла давно два целых числа \(n\) и \(T\) (\(1 \le n \le 100\,000\), \(1 \le T \le 10^9\)) — количество пирожных и доступное время.
В каждой из следующих \(n\) строк дано по два целых числа \(x_i\) и \(t_i\) (\(1 \le x_i, t_i \le 10^9\)) — координата \(i\)-го пирожного и время, за которое Скрудж может его съесть. Пирожные даны в порядке неубывания координаты, то есть для любых \(i\) и \(j\), таких, что \(i \lt j\) верно, что \(x_i \le x_j\).
В единственной строке выходного файла выведите максимальное количество пирожных, которые Скрудж может успеть съесть за время \(T\).
3 10 1 4 2 5 3 3
2
3 10 1 2 2 2 3 3
3
8 100 1 21 3 10 4 3 5 19 8 8 9 32 50 1 100 1
5
В первом примере Скруджу нужно перейти от точки с координатой \(0\) к точке с координатой \(1\), съесть первое пирожное, потом перейти к точке с координатой \(3\) и съесть третье пирожное.
Первая группа тестов состоит из тестов, для которых выполняются ограничения \(1 \le n \le 20, 1 \le T \le 10^9\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 15 баллов.
Вторая группа тестов состоит из тестов, для которых выполняются ограничения \(1 \le n \le 1\,000, 1 \le T \le 1\,000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Третья группа тестов состоит из тестов, для которых выполняются ограничения \(1 \le n \le 1\,000, 1 \le T \le 10^9\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 25 баллов.
Четвертая группа тестов состоит из тестов, для которых выполняются ограничения \(1 \le n \le 100\,000, 1 \le T \le 10^9\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.