Description

It is autumn again, and the apple tree at TaoTao’s home has borne $n$ fruits. TaoTao goes to pick apples; this time he has a chair of height $a$ centimeters. When he cannot reach with his hand, he will stand on the chair and try again.

Different from the first problem of NOIp 2005 Junior: after moving the stool earlier, TaoTao has only $s$ strength left. Of course, each time he picks an apple, it costs some strength. TaoTao wants to know the maximum number of apples he can pick before $s < 0$.

Now you are given the heights above the ground of the $n$ apples $x_i$, the chair height $a$, TaoTao’s maximum reach $b$, his remaining strength $s$, and the strength needed to pick each apple $y_i$. Find the maximum number of apples TaoTao can pick.

Input Format

Line 1: two numbers, the number of apples $n$ and the strength $s$.

Line 2: two numbers, the chair height $a$ and TaoTao’s maximum reach $b$.

Lines 3 to $3 + n - 1$: each line contains two numbers, the apple height $x_i$ and the strength needed to pick this apple $y_i$.

Output Format

Output a single integer, the maximum number of apples that TaoTao can pick.

8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2

4

Hint

For $100\%$ of the testdata, $n \leq 5000$, $a \leq 50$, $b \leq 200$, $s \leq 1000$, $x_i \leq 280$, $y_i \leq 100$.

Translated by ChatGPT 5