Background

Even if I cannot find the youth outside my body,

I still have to throw myself against the late years within me.

But where is the dark night?

Now there are no stars, no moonlight, and thus no faintness of laughter or the flight of love;

The young people are safe, yet before my eyes there is not even a real dark night.

Despair being emptiness is exactly the same as hope!

——@duanfeitong, excerpt from Lu Xun's Hope.

Problem Description

You are now on a straight road. We may treat this road as a number line. You are currently at the origin of the number line. In addition, there are $n$ check-in points. The coordinate of the $i$-th check-in point is $x_i$, and it will start operating at the $a_i$-th moment after you set off. You can enter and check in at a check-in point only after it has started operating (the time for checking in can be ignored). In each moment, you can move at most $1$ unit. You must arrive at the point with coordinate $f$ at moment $t$ or earlier ($f\le t$). No matter when you arrive at point $f$ within the allowed time, starting from moment $t$ you must stay at point $f$ forever. Find the maximum number of check-in points you can check in at. Note that you do not need to check in according to the numbering order of the check-in points.

Input Format

There are $n+1$ lines in total.

The first line contains three integers $n$, $t$, and $f$.

The next $n$ lines each contain two integers $x_i$ and $a_i$.

Output Format

One line containing a non-negative integer, representing the maximum number of check-in points you can check in at.

3 20 10
7 18
3 5
5 0

2

Hint

Explanation for Sample $\small\text{1}$

One feasible plan is as follows: check in at the third check-in point at moment $5$, then check in at the second check-in point at moment $7$, and finally arrive at the destination at moment $14$. It can be proven that at most $2$ check-in points can be checked in at.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $1\leq n\leq 10^6$, $0\leq f\leq t\leq 10^{18}$, $0\leq x_i\leq f$, $0\leq a_i\leq t$, and it is not guaranteed that the coordinates of the check-in points are all distinct.

Please note: since the input size is too large when $n$ is close to $10^7$, we decided to adjust the time limit and memory limit on data with $n\leq 10^6$ to replace the evaluation on data with $n\leq 10^7$.

Please note that the input size of this problem is large. It is recommended to use a fast input method.

In my eternal memory,

you smile innocently.

In my young heart,

you are a spark that keeps burning.

——@duanfeitong, excerpt from Qi Zi's Childhood.

Translated by ChatGPT 5