All is not well in Night City. The robber robbed the bank, which is located in the n-story building, and is now trying to escape using a helicopter on the roof. The floors in the house are numbered from 0 to n - 1, and the roof is considered floor number n. Now law enforcement agencies are on the ground floor, along with the robber.

The robber has a special chip that allows him to knock out police robots at the moment when the robber and the police are on the same floor at the same time. The efficiency of the chip depends on the electric fields of the floor on which it was used. Namely, if, being on the i-th floor, the robber used the chip k times (k a positive integer), then k * qi units of energy is spent, and the police will be stopped for k * ti minutes, and only after that they will continue to move.

The robber ascends at a rate of one floor per minute, while his pursuers ascend at a rate of two floors per minute. Every time the police and the robber are on the same floor at the same time, the robber must use the chip at least once, otherwise the police will catch him. If the police catch up with the robber between floors, he will not be able to use the chip and will be captured.

To safely leave the building, the robber must be on the roof strictly before the police. What is the minimum amount of energy he has to spend to achieve this?

Input

The first line contains one integer n (1 ≤ n ≤ 105).

The next n lines contain two integers qi and ti (1 ≤ qi ≤ 109, 1 ≤ t [i] ≤ 3).

Output

Print a single integer - the minimum amount of energy the robber will have to spend to safely get to the roof.

Note

On the zero floor, the robber must use the chip, spending five units of energy. In a minute, he will be on the first floor, and his pursuers will start moving. Then in another minute they will be on the second floor, where the robber must use the chip again. For this, he will spend another five units of energy. Then in a minute he'll be on the roof, and he'll be able to leave the building safely. As a result, he will spend 5 + 5 = 10 units of energy.