P1478 TaoTao Picks Apples (Upgraded Version)

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.

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 a single integer, the maximum number of apples that TaoTao can pick.

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