P4823 [TJOI2013] Saving the Dwarfs

A group of dwarfs fell into a very deep pit. Because they are too short to climb out, they decide to build a human ladder. That is, one dwarf stands on another dwarf’s shoulders, until the dwarf at the top can touch the edge of the pit with his arms fully stretched. For each dwarf, we know his height from feet to shoulders $A_i$, and his arm length $B_i$. The pit depth is $H$. If we use dwarf $1$, dwarf $2$, dwarf $3$, $\dots$, dwarf $k$ to build a ladder that satisfies $A_1+A_2+A_3+\dots+A_k+B_k \geq H$, then dwarf $k$ can leave the pit and escape. Once a dwarf escapes, he cannot be used to build the human ladder anymore. We want as many dwarfs as possible to escape. Find the maximum number of dwarfs that can escape.

The first line contains an integer $N$, the number of dwarfs. The next $N$ lines each contain two integers $A_i$ and $B_i$. The last line contains $H$.

Output one integer, the maximum number of dwarfs that can escape.

For $30\%$ of the testdata, $N\leq 200$. For $100\%$ of the testdata, $1 \leq N\leq 2000$, $1 \leq A_i,B_i,H\leq10^5$. Translated by ChatGPT 5