问题
您正在玩电子游戏。在这个游戏中有一个地牢 N + 2 房间位于一条直线上。每个房间的编号从 0 to N+1 按顺序。您可以从一个房间移动到相邻的房间。您现在在 1 号房间。0。你的目标是到达房间号。(N + 1) 受到的伤害最小。
房间号0 和编号。(N + 1) 是空房间。在每个房间中从No。1 至编号N,有一个物品或一个怪物。 你被给予 N 一对整数,分别表示每个房间的内容。 对于每个 i (1 \leq i \leq N),整数 A_i, B_i 含义如下。
- 当 A_i = 0,有 在 1 号房间设置了诱杀装置的 1 键。i。 如果你拿起那把钥匙 来自陷阱的 B_i 点伤害。 您可以选择不拿起钥匙,这样您就不会受到任何伤害。
- 当 A_i = 1,有 在 1 号房间设置了诱杀装置的 1 房间内的宝箱i。 宝箱里有一个水晶,可以增加你的 DEF 参数 B_i 点。您可以消费 1 键打开宝箱并增加你的防御力。 你可以选择不打开宝箱,这样你就不会消耗钥匙,并保持你的DEF参数不变。 您的初始 DEF 参数是 0.
- 当 A_i = 2,1号房间里有怪物。i。 当你第一次进入那个房间时,你必须与那个怪物战斗,并采取 B_i - (\rm{player's\ DEF\ at\ that\ time}) 点伤害。 当你在第一次战斗后访问房间时,房间里没有怪物,你也不会受到伤害。
你从房间号开始。0。计算到达 1 号房间所需的最小伤害。(N + 1)
注意,你可以回到你访问过的房间,并且陷阱所造成的伤害不会因为你的DEF参数而减少。
输入
N A_1 B_1 A_2 B_2 : A_N B_N
- 在第一行,您将得到一个整数 N (1 \leq N \leq 900),表示地牢的房间数为 N + 2.
-
关于以下内容 N 行您将得到两个整数 A_i (0 \leq A_i \leq 2), B_i (0 \leq B_i \leq 10^9)以空格分隔,每个房间的信息。的 i第行告诉房间号的内容。i。这些信息保证满足以下条件。
- 各类房间数量小于 300.
- 即使你获得了副本中的所有水晶,来自怪物的伤害也不会低于 0。这意味着,让 X 总和 B_i 对于所有人 i 满足 A_i = 1。对于任何 j 满足 A_j = 2, B_j \geq X 成立。
输出
输出一行,其中包含您到达 1 号房间时受到的最小伤害。(N + 1) 从房间号开始0。 确保在输出末尾插入换行符。
输入示例 1
4 1 2 2 3 0 1 2 2
输出示例 1
4
最佳移动如下。
- 首先去房间号。3 并拿走钥匙。路上,你带着 3 号房间内的怪物造成的伤害点数2,和 1 号房间的诱杀装置造成的伤害点3.
- 接下来,回到1号房间。1,打开宝箱,防御力增加 2 点。沿着这条路你会经过No. 房间。2,但你已经打败了怪物,所以你不会受到伤害。
- 终于到达目标了,房间号。5。这样你就可以和1号房间的怪物战斗了。4,但是感谢您 2 DEF参数的点,你取 0 点伤害。
输入示例 2
4 1 2 2 3 0 4 2 2
输出示例 2
5
这种情况与示例 1 类似,但诱杀装置造成的伤害很大,因此最佳策略是忽略该关键点。
输入示例3
7 0 4 1 3 2 10 1 6 2 9 0 5 2 10
输出示例 3
21