N = int(input())
books = [list(map(int, input().split())) for _ in range(N)]


def isOK(k):
    dp = [[False]*N for _ in range(1 << N)]
    for i in range(N):
        dp[1 << i][i] = True

    for s in range(1 << N):
        for u in range(N):
            if not s & (1 << u) and s != 0:
                continue
            if not dp[s][u]:
                continue
            for v in range(N):
                if s & (1 << v):
                    continue
                if books[u][1]-books[u][0]+books[v][0] > k:
                    continue
                dp[s | (1 << v)][v] |= dp[s][u]

    return sum(dp[-1]) > 0


l = 0
r = 17002
while r-l > 1:
    mid = (l+r)//2
    if isOK(mid):
        r = mid
    else:
        l = mid
print(r)