Problem Description

“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.

Input Format

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.

Output Format

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$.

4
3 5
5 1
3 2
4 6

3
8

Hint

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