问题

你正在玩一个视频游戏。在这个游戏中，有一个地牢，地牢上有 $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$ 号房间中有一个宝箱。在宝箱中有一个水晶，可以增加你的防御参数 $B_i$ 点。你可以消耗 $1$ 把钥匙打开宝箱并增加你的防御。你可以选择不打开宝箱，在这种情况下你不会消耗钥匙，保持你的防御参数不变。你的初始防御参数为 $0$。
• 当 $A_i = 2$ 时，第 $i$ 号房间里有一个怪物。当你首次进入该房间时，你必须与那个怪物战斗，并受到 $B_i - (\rm{此时玩家的防御值})$ 点伤害。当你再次访问该房间时，房间里没有怪物，你不会受到伤害。

你从第 $0$ 号房间开始。计算你到达第 $(N + 1)$ 号房间所受到的最少伤害。

请注意，你可以返回已经访问过的房间，而且陷阱造成的伤害不能通过你的防御参数减少。

输入

$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$ 是满足 $A_i = 1$ 的所有 $i$ 对应的 $B_i$ 的和。对于任何满足 $A_j = 2$ 的 $j$，有 $B_j \geq X$。

输出

输出一行，包含到达第 $(N + 1)$ 号房间所受到的最少伤害。确保在输出末尾插入一个换行符。

输入示例 1

4
1 2
2 3
0 1
2 2

输出示例 1

4

最佳移动路径如下：

• 首先去到第 $3$ 号房间并拿起钥匙。在途中，你从第 $2$ 号房间的怪物受到 $3$ 点伤害，并且从第 $3$ 号房间的陷阱受到 $1$ 点伤害。
• 接下来，返回第 $1$ 号房间，打开宝箱，将你的防御值增加 $2$ 点。在这个过程中，你经过了第 $2$ 号房间，但你已经击败了怪物，所以你不会受到伤害。
• 最后去到目标，第 $5$ 号房间。在这个过程中，你与第 $4$ 号房间的怪物战斗，但由于你的 $2$ 点防御参数，你不会受到伤害。

输入示例 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