← 返回题目列表

Codeforces · 1886/F

F. 钻石失窃

中文机器翻译题面 查看原题

Monocarp 是 Berland 最著名的小偷。这一次,他决定偷两颗钻石。不幸的是,对于 Monocarp 来说,有 $$$n$$$ 摄像机监控钻石。每个相机都有两个参数,$$$t_i$$$ 和 $$$s_i$$$。第一个参数确定摄像机是仅监控第一颗钻石 ($$$t_i=1$$$)、仅监控第二颗钻石 ($$$t_i=2$$$) 还是同时监控两个钻石 ($$$t_i=3$$$)。第二个参数决定相机被黑客攻击后将被禁用的秒数。

每秒,Monocarp 可以执行以下三个操作之一:

- 不执行任何操作;
- 选择一个相机并破解它;如果 Monocarp 破解了第 $$$i$$$ 摄像头,则该摄像头将在接下来的 $$$s_i$$$ 秒内被禁用(如果当前秒是第 $$$T$$$ 秒,则摄像头将从第 $$$(T+1)$$$ 秒到第 $$$(T+s_i)$$$ 秒被禁用,包括在内);
- 如果监控钻石的所有摄像头当前均已禁用,则窃取钻石。如果 Monocarp 还没有偷走第一颗钻石,他就无法偷走第二颗钻石。

请注意,Monocarp 可以多次破解相机,即使它当前已被禁用。

你的任务是确定 Monocarp 从第一颗钻石开始窃取两颗钻石所需的最短时间,或者报告这是不可能的。

输入

第一行包含一个整数 $$$n$$$ ($$$0 \le n \le 1500$$$) — 摄像头数量。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 行包含两个整数 $$$t_i$$$ 和 $$$s_i$$$ ($$$1 \le t_i \le 3$$$; $$$1 \le s_i \le 2n$$$) — 第 $$$i$$$ 相机的参数。

输出

打印一个整数 - Monocarp 先偷走第一颗钻石,然后偷走第二颗钻石所需的最短时间。如果不可能,则打印-1。

示例

输入 #1

4
2 6
1 2
1 2
2 1

输出 #1

6

输入 #2

4
2 8
3 2
3 2
3 5

输出 #2

9

输入 #3

2
3 2
2 3

输出 #3

4

输入#4

1
3 1

输出#4

4

输入 #5

8
2 1
2 2
3 5
3 6
1 2
1 3
1 4
1 5

输出 #5

11