Background

A simple problem is introduced as a warm-up.

Suppose you are standing on a building of height $200m$, and the size of a person can be ignored.

At heights $100m$ and $200m$ of the building, there is an infinitely long steel pipe sticking out, and you can safely stand on it by default.

You have a pair of scissors and a very thin rope of length $150m$. You can tie dead knots, but you cannot tie slip knots, and the size of the knots can be ignored. The question is how to safely get down to the ground.

Solution:

A $150m$ rope is not enough for us to go down directly, so we must use the second steel pipe. So we consider arranging the rope like this:

That is, cut the rope into two parts of $50m$ and $100m$. Tie a small loop at the end of the $50m$ rope, then pass the $100m$ rope through the small loop and connect its two ends. In this way, we make a $100m$ rope.

Tie the other end of the $50m$ rope to the first steel pipe, use it to go down to the second steel pipe, cut off the loop with the scissors, and pull out the $100m$ rope, then you can go down to the ground smoothly. We call this method the "loop-and-chain" method.

The following is a diagram of the whole process.

Note: The circles in the diagram represent the small loops tied at the ends of the rope. The actual size can be ignored.

In the "loop-and-chain" method, we split the rope into two parts: the loop and the chain. The loop can be recovered and reused.

In the following problem setting, we assume only two methods are available: the "loop-and-chain" method and the "simplified loop-and-chain" method. The "simplified loop-and-chain" method means the loop length is $0$ or the chain length is $0$.

(Thanks to huzheng20 for providing the pictures Orz)

Problem Description

There are $n$ steel pipes on a building. The $i$-th steel pipe has height $h_i$ and value $v_i$. You are on some steel pipe with the greatest height. You have a pair of scissors and a rope, and the values of the steel pipes you step on must form a monotonic non-decreasing sequence.

Some steel pipes may have the same height, which means at that height you can choose steel pipes with different values to stand on.

The initial length of your rope must be a positive integer, but after using the loop-and-chain method you may recover a rope with a non-integer length.

Find the minimum rope length needed to get down to the ground.

Input Format

The first line contains one positive integer $n$, the number of steel pipes.

The next $n$ lines each contain two positive integers $h_i, v_i$, representing the height and value of the $i$-th steel pipe.

Output Format

Output one positive integer in one line, the minimum rope length required.

3
100 7
63 9
25 8

69

10
99 191
30 82
144 52
11 0
149 70
65 117
73 37
39 101
135 92
43 33

99

Hint

This problem uses bundled testdata.

For $10\%$ of the testdata, from high to low, the values of the steel pipes form a monotonic non-increasing sequence.

For another $10\%$ of the testdata, $n \le 10^4$.

For another $40\%$ of the testdata, $n \le 10^5$ and there do not exist indices $i, j$ such that $h_i = h_j$ or $v_i = v_j$.

For all testdata, $1 \le n \le 5 \times 10^5$, $1 \le h, v \le 10^{18}$.

Translated by ChatGPT 5