题目描述

手工课上，老师拿出 $n$ 块积木，它们的长度不定，宽度是 $1$ 或 $2$。现在他要把同学们把这些积木放入一个 $2 \times m$ 的积木盒里（要求全部横放，不允许堆放、斜放），请你帮助小 K 计算，能容纳所有积木的最小 $m$ 值。

输入格式

第一行为正整数 $n$，表示积木数，接下来 $n$ 行，每行两个正整数 $a$ 和 $b$，分别表示每块积木的宽和长。

输出格式

输出 $m$ 的最小值。

输入数据#1

3
1 2
2 2
2 3

输出数据#1

7

解释#1

样例1中，三块积木的摆放方式如下图所示：其中 $1 \times 2$ 的积木只能横放，不能斜放或堆放。

输入数据#2

3
1 2
1 2
1 3

输出数据#2

4

数据范围

$10\%$ 的数据 $a = 2$

$100\%$ 的数据中，$n \leq 1000$，$a = 1$ 或 $2$，$b \leq 100$。