"Beads and flowers, how many tears in the world..."

Pendants have long been used as ornaments. Their graceful, swaying motion displays a unique elegance and nobility. Our protagonist, Xiao Q, wants to buy a beautiful pendant to decorate her dormitory.

A pendant is composed of several beads connected together. Each bead consists of three parts: the bead itself, a connecting ring above the bead, and a hook below the bead (as shown in the figure below). We can simply assume that the $i$-th bead from top to bottom has its connecting ring attached to the hook of the bead above it (the $(i-1)$-th bead, except for the first one). Xiao Q wants to buy a pendant that is long enough to look more charming.

However, the shopkeeper tells Xiao Q that a pendant cannot be arbitrarily long because every bead is subject to gravity, exerting a certain tension on the hook above it, and the hook has a limited load-bearing capacity. The shopkeeper also tells Xiao Q that he has a total of $N$ beads (assume every bead is beautiful and Xiao Q likes them all), and each bead has its own weight and load-bearing capacity. A pendant is stable if and only if, for every bead in it, the sum of the weights of all beads below it (excluding itself) does not exceed the load-bearing capacity of its hook.

Xiao Q wants her pendant to be as long as possible. Can you help her calculate the maximum possible length of a stable pendant? Of course, if there are multiple options, Xiao Q wants the one with the minimum total weight.

Input

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

Output

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

Examples

Input 1

4
3 5
5 1
3 2
4 6

Output 1

3
8

Subtasks

Each test case is scored individually. For each test case: If the pendant length $L$ matches the answer and the minimum total weight $W$ is also correct, you get 10 points. If the pendant length $L$ matches the answer but the minimum total weight $W$ is incorrect, you get 4 points. * Otherwise, you get 0 points.

Constraints

For 30% of the data, $N \le 10000$. For 100% of the data, $N \le 200000$. For all data, $W_i, C_i \le 2^{31}$.