题目描述

Shaass 拥有 $n$ 本书。他想为他的所有书制作一个书架，并想让书架的长宽尽量小。第 $i$ 本书的厚度是 $t_i$，且这本书的纸张宽度是 $w_i$。书的厚度是 $1$ 或 $2$，所有书都有同样的高度（即书架的高是均匀的）。

Shaass 以以下的方式摆放这些书籍。

1. 他选择了一些书并竖直摆放它们。
2. 他将剩余的书籍水平纺织于竖直的书上面。

水平放置的书的宽度和不能多于竖直放置的书的总厚度。图中描绘了书籍的示例排列。

帮助 Shaass 找到可以达到的书架长度最小值。

输入格式

第一行包含一个整数 $n$，$1\le n\le 100$。

下面的 $n$ 行分别为 $t_i$ 和 $w_i$，对应了书的长度和宽度（即书籍竖直放置与水平放置所占的空间），$1\le t_i\le 2$，$1\le w_i\le 100$。

输出格式

一个整数，为可以达到的最小的长度。

5
1 12
1 3
2 15
2 5
2 1

5

3
1 10
2 1
2 4

3