Shaass and Bookshelf

# 题目描述 Shaass拥有n本书。他想为他的所有书制作一个书架，并想让书架的长宽尽量小。第i本书的厚度是t[i]，且这本书的纸张宽度是w[i]。书的厚度是1或2，所有书都有同样的高度（即书架的高是均匀的）。 Shaass以以下的方式摆放这些书籍。 1.他选择了一些书并竖直摆放它们。 2.他将剩余的书籍水平纺织于竖直的书上面。 水平放置的书的宽度和不能多于竖直放置的书的总厚度。图中描绘了书籍的样本排列。 帮助Shaass找到可以达到的书架长度最小值。 # 输入格式： 输入的第一行包含一个int型的整数n（1<=n<=100）。 下面的n行分别为v[i]和w[i]，对应了书的长度和宽度（即书籍竖直放置与水平放置所占的空间）。 （1<=t[i]<=2,1<=w[i]<=100) # 输出格式： 一个整数，为可以达到的最小的长度。 ------------ ###### 翻译提供：masiyuan

Shaass has $ n $ books. He wants to make a bookshelf for all his books. He wants the bookshelf's dimensions to be as small as possible. The thickness of the $ i $ -th book is $ t_{i} $ and its pages' width is equal to $ w_{i} $ . The thickness of each book is either $ 1 $ or $ 2 $ . All books have the same page heights. Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure. Help Shaass to find the minimum total thickness of the vertical books that we can achieve.

The first line of the input contains an integer $ n $ , $ (1<=n<=100) $ . Each of the next $ n $ lines contains two integers $ t_{i} $ and $ w_{i} $ denoting the thickness and width of the $ i $ -th book correspondingly, ( $ 1<=t_{i}<=2,1<=w_{i}<=100 $ ).

On the only line of the output print the minimum total thickness of the vertical books that we can achieve.

5
1 12
1 3
2 15
2 5
2 1

5

3
1 10
2 1
2 4

3