Problem Description

Input Format

$ 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 Format

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.

Sample Input and Output

Sample Input #1

4
1 2
2 3
0 1
2 2

Sample Output #1

4

Sample Input #2

4
1 2
2 3
0 4
2 2

Sample Output #2

5

Sample Input #3

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

Sample Output #3

21

Notes/Hints

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 - (\text{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.

Sample Explanation 1

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.

Sample Explanation 2

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 部分

见题面 Output 部分