AT_code_festival_china_h Dungeon

[problemUrl]: https://atcoder.jp/contests/code-festival-2014-china-open/tasks/code_festival_china_h

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

### 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. ### 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.