P5909 [CTSC2007] Pendant

“Beads decorate the flower core; how many sour tears in this world”…… Pendants have long been used as decorations. Their hanging charm and gorgeous swinging movement show a unique elegance and nobility. Our main character, Xiao Q, wants to buy a beautiful pendant to decorate the dormitory. A pendant is made by connecting several beads. Each bead has three parts: the bead itself, a connecting ring above it, and a hook below it. We can simply think that the $i$-th bead from top to bottom is made by putting its connecting ring onto the hook of the bead above it (that is, the $(i-1)$-th bead), except for the first one. Xiao Q wants to buy a pendant that is long enough, so it looks more charming. However, the shop owner tells Xiao Q that a pendant cannot be arbitrarily long, because each bead is affected by gravity and thus applies a certain pulling force to the hook above it, and the hook has limited capacity. The owner also tells Xiao Q that he has a total of $N$ beads (assume every bead is very beautiful and Xiao Q likes all of them), and each bead has its own weight and load capacity. **A pendant is stable if and only if, for every bead on it, the total weight of all beads below it (excluding itself) does not exceed the capacity of its hook.** Xiao Q wants the pendant to be as long as possible. Please help compute the maximum possible length of a stable pendant. Of course, if there are multiple choices, Xiao Q wants the one with the minimum total weight.

The first line contains a positive integer $N$, representing the number of beads in the shop. The next $N$ lines each contain two integers $C_i$, $W_i$, representing the capacity and weight of the $i$-th bead, respectively.

There are two lines in total. The first line contains an integer $L$, representing the maximum length of a stable pendant that can be found. The second line contains an integer $W$, representing the minimum total weight among all stable pendants of length $L$.

For $30\%$ of the testdata, $N \le 10^4$. For $100\%$ of the testdata, $N \le 2 \times 10^5$, $W_i, C_i \le 2^{31}$. Translated by ChatGPT 5