虎哥有n本书，他想为他所有的书做一个书架。他希望书架的尺寸尽可能小。第i本书的厚度为ti，宽度为wi。每本书的厚度为1或2。所有的书都有相同的高度。

虎哥在书架上摆放书的方式如下。首先，他选择了一些书，并将它们垂直放置。然后他把剩下的书水平地放在垂直的书上面。水平书籍的宽度之和不得超过垂直书籍的总厚度。图中描绘了书籍的示例排列。

现在请你帮他找到按上述方法摆放所能达到的垂直书籍的最小总厚度。

第1行为一个整数n(1≤n≤100),接下来的n行，每行包含两个整数ti和wi，分别表示第i本书的厚度与宽度 (1≤ti≤2, 1≤wi≤100)。

仅有一个整数，表示最小的总厚度。

5
1 12
1 3
2 15
2 5
2 1

5

样例2：
输入：
3
1 10
2 1
2 4
输出
3