Shaass 有 n 本书。他想为他所有的书制作一个书架。他希望书架的尺寸尽可能小。第 i 本书的厚度为 ti,页宽等于 wi。每本书的厚度为 1 或 2。所有书籍的页高相同。
Shaass 按以下方式将书放在书架上。首先,他选择了一些书并将它们垂直放置。然后他将其余的书水平地放在垂直书的上方。横向书籍的宽度之和不得大于纵向书籍的总厚度。图中描绘了书籍的示例排列。
帮助 Shaass 找到我们可以实现的垂直书籍的最小总厚度。
输入
输入的第一行包含一个整数 n,(1 ≤ n ≤ 100)。接下来的n行每行包含两个整数ti和wi,分别表示第i本书的厚度和宽度,(1≤ti≤2,1≤wi≤100)。
输出
在输出的唯一一行上打印我们可以实现的垂直书籍的最小总厚度。
示例
输入 #1
5 1 12 1 3 2 15 2 5 2 1
输出 #1
5
输入 #2
3 1 10 2 1 2 4
输出 #2
3