题目描述

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

输入格式

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

输出格式

输出m的最小值

输入样例1

3
1 2
2 2
2 3

输出样例1

7

输入样例2

3
1 2
1 2
1 3

输出样例2

4

样例说明

数据范围

100%数据: n<=1000，a=1或2，b<=100