H - Dungeon 解説 /

実行時間制限: 5 sec / メモリ制限: 256 MB

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