← 返回题目列表

Codeforces · 294/B

B. 沙斯和书架

中文机器翻译题面 查看原题

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