Problem

You are playing a video game. In this game there is a dungeon with $N + 2$ rooms placed on a straight line. Each room is numbered from $0$ to $N+1$ in order. You can move from one room to a neighboring room. You are now at room No.$0$. Your goal is to reach room No.$(N + 1)$ with least damage taken.

The room No.$0$ and No.$(N + 1)$ are empty rooms. In each of the room from No.$1$ to No.$N$, there is an item or a monster. You are given $N$ pairs of integers which tells the contents of each room respectively. For each $i$ ($1 \\leq i \\leq N$), the integers $A_i$, $B_i$ means as following.

• When $A_i = 0$, there is $1$ key on which a booby-trap is set in the room No.$i$. If you pick up that key you take $B_i$ points of damage from the trap. You may choose not to pick up the key, in which case you take no damage.
• When $A_i = 1$, there is $1$ treasure box in the room No.$i$. In the treasure box there is a crystal that increases your DEF parameter by $B_i$ points. You can consume $1$ key to open the treasure box and increase your DEF. You may choose not to open the treasure box, in which case you don't consume a key, and keep your DEF parameter as is. Your initial DEF parameter is $0$.
• When $A_i = 2$, there is a monster in the room No.$i$. You must fight that monster when you first entered that room, and take $B_i - (\\rm{player's\\ DEF\\ at\\ that\\ time})$ points of damage. When you visit the room after that first battle, there is no monster in the room, and you take no damage.

You start from the room No.$0$. Calculate the least damage you take to reach the room No.$(N + 1)$

Note that you can go back to the room you have visited, and the damage taken from the booby-trap can't be decreased by your DEF parameter.

Input

$N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$

• On the first line, you will be given an integer $N$ ($1 \\leq N \\leq 900$), which means the number of rooms in the dungeon is $N + 2$.
• On the following $N$ lines you will be given two integers $A_i$ ($0 \\leq A_i \\leq 2$), $B_i$ ($0 \\leq B_i \\leq 10^9$) separated by space, the information of each room. The $i$-th line tells the contents of the room No.$i$. These information are guaranteed to meet the following conditions.
  • The number of each kind of rooms is less than $300$.
  • Even if you acquire all the crystals in the dungeon, the damage taken from a monster will not be less than $0$. That means, let $X$ the sum of $B_i$ for all $i$ which satisfies $A_i = 1$. For any $j$ which satisfies $A_j = 2$, $B_j \\geq X$ holds.

Output

Output a single line containing the least damage you take to reach the room No.$(N + 1)$ starting from the room No.$0$. Make sure to insert a line break at the end of the output.

Input Example 1

4
1 2
2 3
0 1
2 2

Output Example 1

4

Optimal move is as following.

• At first go to room No.$3$ and take the key. On the way, you take $3$ points of damage from the monster in the room No.$2$, and $1$ point of damage from a booby-trap at the room No.$3$.
• Next, go back to room No.$1$, open the treasure box, increase your DEF by $2$ points. On this way you pass the room No.$2$, but you have already beaten the monster so you take no damage.
• Finally go to the goal, room No.$5$. On this way you fight the monster at the room No.$4$, but thanks to your $2$ points of DEF parameter, you take $0$ points of damage.

Input Example 2

4
1 2
2 3
0 4
2 2

Output Example 2

5

This case is similar to the Example 1, but the damage from the booby-trap is large so the optimal move is to ignore the key.

Input Example 3

7
0 4
1 3
2 10
1 6
2 9
0 5
2 10

Output Example 3

21