2068 - 藏经阁
Description
大唐藏经阁的地图类拥有n本地图册。
藏经阁想为地图类的所有书制作一个书架，并想让书架的长宽尽量小。第i本书的厚度是v[i]，且这本书的纸张宽度是w[i]。书的厚度是1或2，所有书都有同样的高度（即书架的高是均匀的）。
藏经阁的官员想了以下的方式摆放这些书籍。
>1.他选择了一些书并竖直摆放它们。
>2.他将剩余的书籍水平放置于竖直的书上面。
水平放置的书的宽度和不能多于竖直放置的书的总厚度。图中描绘了书籍的样本排列。
帮助藏经阁找到可以达到的书架长度最小值minlen。
Input
输入的第一行包含一个整数n。
下面的n行分别为v[i]和w[i]，对应了书的长度和宽度（即书籍竖直放置与水平放置所占的空间）。
（1<=t[i]<=2,1<=w[i]<=100)
Output
一个整数，为可以达到的最小的长度。
Examples
Input
5 1 12 1 3 2 15 2 5 2 1
Output
5
Input
3 1 10 2 1 2 4
Output
3
Hint
30%数据，6\leq n \leq 20
100%数据，n \leq 500,总厚度 \leq 10^5