310780: CF1886F. Diamond Theft

F. Diamond Thefttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Monocarp is the most famous thief in Berland. This time, he decided to steal two diamonds. Unfortunately for Monocarp, there are $n$ cameras monitoring the diamonds. Each camera has two parameters, $t_i$ and $s_i$. The first parameter determines whether the camera is monitoring the first diamond only ($t_i=1$), the second diamond only ($t_i=2$), or both diamonds ($t_i=3$). The second parameter determines the number of seconds the camera will be disabled after it is hacked.

Every second, Monocarp can perform one of the following three actions:

• do nothing;
• choose a camera and hack it; if Monocarp hacks the $i$-th camera, it will be disabled for the next $s_i$ seconds (if the current second is the $T$-th one, the camera will be disabled from the $(T+1)$-th to the $(T+s_i)$-th second, inclusive);
• steal a diamond if all cameras monitoring it are currently disabled. Monocarp cannot steal the second diamond if he hasn't stolen the first diamond yet.

Note that Monocarp can hack a camera multiple times, even if it is currently disabled.

Your task is to determine the minimum time it will take Monocarp to steal both diamonds, beginning with the first diamond, or report that it is impossible.

Input

The first line contains a single integer $n$ ($0 \le n \le 1500$) — the number of cameras.

Then $n$ lines follow, the $i$-th of them contains two integers $t_i$ and $s_i$ ($1 \le t_i \le 3$; $1 \le s_i \le 2n$) — the parameters of the $i$-th camera.

Output

Print a single integer — the minimum time it will take for Monocarp to steal the first diamond first and then the second diamond. If it is impossible, print -1.

ExamplesInput

4
2 6
1 2
1 2
2 1

Output

6

Input

4
2 8
3 2
3 2
3 5

Output

9

Input

2
3 2
2 3

Output

4

Input

1
3 1

Output

4

Input

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

Output

11

题目大意：
单卡拉普是贝尔兰最著名的盗贼。这次，他决定偷两颗钻石。不幸的是，有n台摄像头监控着这些钻石。每台摄像头都有两个参数，$t_i$ 和 $s_i$。第一个参数决定了摄像头是否只监控第一颗钻石（$t_i=1$），只监控第二颗钻石（$t_i=2$），或者同时监控两颗钻石（$t_i=3$）。第二个参数决定了摄像头被黑掉后失效的秒数。

每秒钟，单卡拉普可以执行以下三种操作之一：
1. 什么都不做；
2. 选择一个摄像头并黑掉它；如果单卡拉普黑掉了第i个摄像头，它将在接下来的$s_i$秒内失效（如果当前秒是第T秒，摄像头将从第T+1秒失效到第T+s_i秒，包括第T+s_i秒）；
3. 如果所有监控它的摄像头当前都失效了，就偷一颗钻石。如果单卡拉普还没有偷到第一颗钻石，他就不能偷第二颗钻石。

注意，即使摄像头当前失效，单卡拉普也可以多次黑掉它。

任务是确定单卡拉普偷走两颗钻石所需的最短时间，或者报告无法做到。

输入输出数据格式：
输入：
- 第一行包含一个整数$n$（$0 \le n \le 1500$）——摄像头的数量。
- 接下来n行，每行包含两个整数$t_i$和$s_i$（$1 \le t_i \le 3$；$1 \le s_i \le 2n$）——第i个摄像头的参数。

输出：
- 打印一个整数——单卡拉普先偷第一颗钻石再偷第二颗钻石所需的最短时间。如果不可能，打印-1。题目大意： 单卡拉普是贝尔兰最著名的盗贼。这次，他决定偷两颗钻石。不幸的是，有n台摄像头监控着这些钻石。每台摄像头都有两个参数，$t_i$ 和 $s_i$。第一个参数决定了摄像头是否只监控第一颗钻石（$t_i=1$），只监控第二颗钻石（$t_i=2$），或者同时监控两颗钻石（$t_i=3$）。第二个参数决定了摄像头被黑掉后失效的秒数。 每秒钟，单卡拉普可以执行以下三种操作之一： 1. 什么都不做； 2. 选择一个摄像头并黑掉它；如果单卡拉普黑掉了第i个摄像头，它将在接下来的$s_i$秒内失效（如果当前秒是第T秒，摄像头将从第T+1秒失效到第T+s_i秒，包括第T+s_i秒）； 3. 如果所有监控它的摄像头当前都失效了，就偷一颗钻石。如果单卡拉普还没有偷到第一颗钻石，他就不能偷第二颗钻石。 注意，即使摄像头当前失效，单卡拉普也可以多次黑掉它。 任务是确定单卡拉普偷走两颗钻石所需的最短时间，或者报告无法做到。 输入输出数据格式： 输入： - 第一行包含一个整数$n$（$0 \le n \le 1500$）——摄像头的数量。 - 接下来n行，每行包含两个整数$t_i$和$s_i$（$1 \le t_i \le 3$；$1 \le s_i \le 2n$）——第i个摄像头的参数。 输出： - 打印一个整数——单卡拉普先偷第一颗钻石再偷第二颗钻石所需的最短时间。如果不可能，打印-1。