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