AT_code_festival_china_h Dungeon

你正在玩一款视频游戏。这个游戏中有一个地下城，包含 $N + 2$ 个按顺序排列的房间，编号从 $0$ 到 $N+1$。你可以在相邻的房间之间移动。你当前在房间 $0$，目标是以最小的伤害到达房间 $N+1$。 房间 $0$ 和房间 $N+1$ 是空的。从房间 $1$ 到房间 $N$ 的每个房间中都有一个物品或怪物。每个房间的具体内容用 $N$ 对整数表示，对于第 $i$ 个房间（$1 \leq i \leq N$），整数 $A_i$ 和 $B_i$ 的含义如下： - 如果 $A_i = 0$，房间 $i$ 中有一个带陷阱的钥匙。捡起钥匙会受到 $B_i$ 的伤害。你也可以选择不捡，那么就不会受伤。 - 如果 $A_i = 1$，房间 $i$ 拥有一个宝箱，里面有水晶，可以将你的防御值（DEF）增加 $B_i$ 点。你可以用一把钥匙打开宝箱来增加防御值，或者选择不打开，这样不会消耗钥匙，防御值保持不变。最初你的防御值是 $0$。 - 如果 $A_i = 2$，房间 $i$ 中有怪物。首次进入该房间时必须和怪物战斗，承受 $B_i - \text{（当前防御值）}$ 的伤害。此后，再次进入时怪物已消失，不会再受伤。 从房间 $0$ 出发，计算到达房间 $N+1$ 的最小受伤值。 注意：你可以返回到已经进入过的房间，并且增加的防御值不能减少因陷阱造成的伤害。

第一行输入一个整数 $N$（$1 \leq N \leq 900$），表示地下城房间的数量为 $N + 2$。 接下来的 $N$ 行中，每行用空格分隔开两个整数 $A_i$ 和 $B_i$（$0 \leq A_i \leq 2$, $0 \leq B_i \leq 10^9$），描述每个房间里的信息。以下条件确保这些信息的有效性： - 每种房间类型最多出现 $300$ 次。 - 即使你获得地下城中的所有水晶，面对怪物仍然会承受不小于 $0$ 点的伤害。也就是说，设总和 $X$ 为所有 $A_i = 1$ 的 $B_i$ 之和。对于所有 $A_j = 2$，都有 $B_j \geq X$ 成立。

输出一行，表示从房间 $0$ 到房间 $N+1$ 所受的最小伤害值，并确保最后有一个换行符。 ### 示例解释 例1中最佳路线如下： - 首先前往房间 $3$ 并捡钥匙。在路上，会在房间 $2$ 被怪物造成 $3$ 点伤害，在房间 $3$ 被陷阱伤害 $1$ 点。 - 然后返回房间 $1$，打开宝箱，获得 $2$ 点的防御。在返回途中经过房间 $2$ 时，因怪物已被击败，所以不会受伤。 - 最后到达目的地房间 $5$。这一次在房间 $4$ 和怪物战斗，但感谢你 $2$ 点的防御值，最终不会受伤。 例2与第一例相似，但由于陷阱损伤较大，最佳策略是放弃捡钥匙。 **本翻译由 AI 自动生成**

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