P2107 Xiao Z's AK Plan

In Xiao Z's hometown, there is a street of computer labs, with many labs. Each lab has ten thousand people solving problems. Xiao Z just finished CodeChef and is going for a walk. There are $n$ computer labs on the street. The $i$-th lab is at coordinate $x_i$, and Xiao Z's home is at $0$. Xiao Z moves at speed $1$, that is, the time from $x_1$ to $x_2$ is $|x_1 - x_2|$. Each lab has a different number of students, and their ACM problem levels vary. After reaching lab $i$, Xiao Z can spend $t_i$ time thinking, and then instantly "AK"; of course, he can also pass by without entering. Xiao Z now has only $m$ units of time. After that, he must hurry to Codeforces. He wants to know the maximum number of labs he can "AK". Please help him.

The first line contains two integers $n, m$. The next $n$ lines each contain two integers $x_i, t_i$.

Output one integer: the maximum number of labs Xiao Z can "AK".

For $30\%$ of the testdata, $n \leq 20$. For $60\%$ of the testdata, $n \leq 1000$. For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $0 \leq m, x_i \leq 10^{18}$, $0 \leq t_i \leq 10^9$. Translated by ChatGPT 5