Magry的烦恼

题目描述

Magry有好多好多书。然而让Magry烦恼的是，大运村宿舍放书的地方实在有限，以至于他要想办法让所有的书占的横向宽度尽量小。

对于Magry手头$n$本书的第$i$本，高度完全相同，厚度为$t_{i}$，宽度为$w_{i}$，且每本书的厚度要么是1，要么是2.如下图所示：

另外，Magry可是个有强迫症的人，他一定要将书这么摆：

• 首先，他需要选一些书竖着摆；
• 其次，他需要将剩下的书横着摆在竖着摆的书的上方摆一层，其宽度之和需要不大于下层竖着摆的书的厚度之和。

如下图所示：

Magry需要知道的是他所有的$n$本书照这样的方式摆所需要的最小宽度$x$。

输入

多组输入数据。

每组数据有n+1行，第一行为一个正整数，为Magry手头书的数目$n$. $1 \leq n \leq 100$

接下来n行，每行2个正整数$t_{i}$，$w_{i}$，以一个空格分隔，分别代表第$i$本书的厚度和宽度，其中$1 \leq t_{i} \leq 2$，$1 \leq w_{i} \leq 100$

输出

对于每组数据，输出一行，最小宽度$x$。

样例

Input

5
1 26
1 8
1 7
1 2
2 4

Output

4