Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

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.

NA_1B_1A_2B_2:A_NB_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.

- The number of each kind of rooms is less than

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.

4 1 2 2 3 0 1 2 2

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.

4 1 2 2 3 0 4 2 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.

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

21