题面描述

「你知道吗？据说学校的钟楼有着某种神秘的力量。如果你按特定的步骤进行操作的话，可以让过去与未来在这里交汇，完成本应无法做到的事情。」

你现在来到了钟楼的内部。你曾经在过去遗失了某个重要的东西，你现在要借助钟楼的力量回到过去，将其找回。

经过你的研究，你知道钟一共有 $n$ 个指针在表盘上不断地旋转。第 $i$ 个指针有两种属性 $t_i,s_i$，其中 $t_i$ 的含义为：

• 如果 $t_i=1$，表示这个指针只存在于现在
• 如果 $t_i=2$，表示这个指针只存在于过去
• 如果 $t_i=3$，表示这个指针同时存在于现在和过去

钟楼内部的时间相对稳定，从 $1$ 时刻起，每一时刻你可以进行如下几种操作之一：

• 你可以选择一个指针 $i$，使其暂时停止转动。但由于钟楼内部构造在维护时间的稳定，如果你在第 $T$ 时刻停止了这个指针，那么这个指针只会在第 $[T+1,T+s_i]$ 个时刻停止转动，在第 $T+s_i+1$ 时刻它会重新开始转动。
• 如果所有存在于现在的指针都已经停止转动，你可以从现在的时间线回到过去的时间线。钟楼内部的时间会经过 $1$ 的时间。
• 如果所有存在于过去的指针都已经停止转动，你可以从过去的时间线返回现在的时间线。钟楼内部的时间会经过 $1$ 的时间。

由于钟楼对时间的效应，你可以认为你找回遗失的东西不花费任何时间。因此你需要做的就是合理地暂停指针，从现在回到过去，然后再返回现在。

如果有多个人的话，这个任务会容易许多，但现在只有你自己。

请计算出最小时间，或者判断无解。

输入格式

第一行一个正整数 $n$，表示指针数量。

接下来 $n$ 行每行两个正整数 $t_i,s_i$，描述每个指针。

输出格式

输出一行一个数，表示完成任务的最少时间，如果无法完成任务则输出 -1。

样例输入输出

输入样例 #1

4
1 2
1 3
3 4
2 1

输出样例 #1

6

如下是一种合法的操作方案：

• 在 $1$ 时刻停止第二个指针

• 在 $2$ 时刻停止第一个指针

• 在 $3$ 时刻停止第三个指针

• 在 $4$ 时刻前往过去

• 在 $5$ 时刻停止第四个指针

• 在 $6$ 时刻返回现在

输入样例 #2

5
1 2
1 3
3 3
2 1
1 3

输出样例 #2

-1

可以证明该情况下不存在合法的方案。

数据范围

Subtask1 (22pts)：$n\le1000$，保证 $t_i=3$ 的个数 $\le7$

Subtask2 (12pts)：$n\le50$

Subtask3 (14pts)：$n\le500$

Subtask4 (24pts)：$n\le3000$

Subtask5 (12pts)：$n\le5000$

Subtask6 (16pts)：$n\le8000$