human
At the school where the twins Ami and Mami attend, the summer vacation has already begun, and a huge amount of homework has been given this year as well. However, the two of them were still trying to go out without doing any homework today. It is obvious that you will see crying on the last day of summer vacation as it is, so you, as a guardian, decided not to leave the house until you finished your homework of reading impressions today with your heart as a demon.

Well-prepared you have already borrowed all the assignment books from the library. However, according to library rules, only one book is borrowed for each book. By the way, for educational reasons, I decided to ask them to read all the books and write their impressions without cooperating with each other. In addition, since the deadline for returning books is near, I decided to have them finish reading all the books as soon as possible. And you decided to think about how to do your homework so that you can finish your homework as soon as possible under those conditions. Here, the time when both the twins finish their work is considered as the time when they finish reading the book and the time when they finish their homework.

Since there is only one book for each book, two people cannot read the same book at the same time. In addition, due to adult circumstances, once you start reading a book, you cannot interrupt it, and once you start writing an impression about a book, you cannot interrupt it. Of course, I can't write my impressions about a book I haven't read. Since Ami and Mami are twins, the time it takes to read each book and the time it takes to write an impression are common to both of them.

For example, suppose that there are three books, and the time it takes to read each book and the time it takes to write an impression are as follows.

| Time to read a book | Time to write an impression
--- | --- | ---
Book 1 | 5 | 3
Book 2 | 1 | 2
Book 3 | 1 | 2


In this case, if you proceed with your homework as shown in Figure C-1, you can...
Using python3 can you solve the prior task?
 Can you provide a the Python program you requested?
assistant
#Here is the Python program you requested.

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f(n):
        a = [LI() for _ in range(n)]
        t = max(map(lambda x: x[0]*2+x[1], a))
        u = sum(map(sum,a))
        mx = max(map(lambda x: [x[0],-x[1]], a))
        mxi = a.index([mx[0], -mx[1]])
        k = sum(map(lambda x: x[0], a)) - mx[0]
        if k < mx[0]:
            mx0 = mx[0]
            dp = [0] * (mx0+1)
            dp[k] = 1
            for ai in range(n):
                if ai == mxi:
                    continue
                c = a[ai][1]
                for i in range(mx0-c,-1,-1):
                    dp[i+c] |= dp[i]
            mt = 0
            for i in range(mx0,-1,-1):
                if dp[i]:
                    mt = i
                    break
            u += (mx0 - mt)
        return max(t,u)

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))

print(main())