题目描述

某大型展览园区中有三个接驳站，分别记为甲站、乙站和丙站。三座车站通过一条单向环形道路连接，车辆只能按照

$$\text{甲站}\to\text{乙站}\to\text{丙站}\to\text{甲站}\to\cdots$$

的顺序行驶。

清晨，$n$ 位参观者和 $3$ 位园区工作人员都在甲站。园区只有一辆小型接驳车，车内至多乘坐 $3$ 人。接驳车初始位于甲站，最终也必须回到甲站。

所有参观者和工作人员都持有驾驶许可，但接驳车行驶时车内必须至少有一人。因此，即使车内只有参观者，也可以正常行驶；若车内无人，则车辆不能自行前往下一站。

一部分参观者的目的地是乙站，另一部分参观者的目的地是丙站。所有参观者只能在甲站上车，并且只能在自己的目的站下车，不能在中途站提前下车。

不同参观者对行驶速度的承受能力不同。编号为 $i$ 的参观者的目的地由 $w_i$ 表示：

• $w_i=1$ 表示其目的地为乙站；
• $w_i=2$ 表示其目的地为丙站。

当编号为 $i$ 的参观者在车上时，接驳车从一个站点行驶到下一个站点所用的时间不得少于 $t_i$ 分钟。若车上有多位参观者，则该段行程必须同时满足所有人的时间限制。

工作人员可以在任意站点上车或下车，也可以多次上下车，但任务结束时，$3$ 位工作人员都必须回到甲站。工作人员接受过专业训练，当车上没有参观者时，从一个站点行驶到下一个站点只需要 $1$ 分钟。

请设计一种运输方案，使所有参观者到达各自的目的地，并使所有工作人员和接驳车最终回到甲站。你需要求出完成全部任务所需的最短时间。

输入格式

第一行包含一个整数 $n$，表示参观者人数。

接下来 $n$ 行，每行包含两个整数 $w_i,t_i$，含义见题目描述。

输出格式

输出一个整数，表示完成全部接驳任务所需的最短时间。

样例

样例 1

样例输入

1
1 5

样例输出

7

样例解释

一种最优方案如下：

• 编号为 $1$ 的参观者与一位工作人员共同乘车，从甲站前往乙站，耗时 $5$ 分钟；
• 该工作人员独自驾驶接驳车从乙站前往丙站，再从丙站返回甲站，共耗时 $1+1$ 分钟。

总时间为 $7$ 分钟。

样例 2

样例输入

6
1 1
1 2
1 3
1 2
2 3
2 1

样例输出

14

数据范围与提示

测试点 $1,2$：$n\leq 10$；
测试点 $3,4,5$：$n\leq 20$；
测试点 $6,7$：所有参观者均满足 $t_i=2$；
测试点 $8,9,10$：所有参观者均满足 $t_i\in\{2,3\}$；
测试点 $11,12$：所有参观者均满足 $1\leq t_i\leq 10$；
测试点 $13$：没有参观者的目的地为乙站；
测试点 $14,15,16$：目的地为乙站的参观者不超过 $5$ 位；
测试点 $17$：没有参观者的目的地为丙站；
测试点 $18,19,20$：目的地为丙站的参观者不超过 $5$ 位；
测试点 $21,22$：$n\leq 1000$；
测试点 $23,24,25$：无特殊限制。

所有测试点满足：

$$1\leq n\leq 50\,000,\qquad 1\leq t_i\leq 1000,\qquad w_i\in\{1,2\}.$$