| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 13 | 8 | 6 | 54.545% |
Сегодня у Скруджа день рождения!
В подарок он получил целый стол пирожных. Так как у миллионеров не очень много свободного времени, Скрудж хочет съесть как можно больше пирожных за $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 < 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ドル$ и съесть третье пирожное.