#region Header
#!/usr/bin/env python3
# from typing import *

import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq


def input():
    return sys.stdin.readline()[:-1]


# sys.setrecursionlimit(1000000)
#endregion

# _INPUT = """3
# 1 4
# 2 4
# 3 4
# """
# sys.stdin = io.StringIO(_INPUT)


def main():
    N = int(input())
    A = [None for _ in range(N)]
    B = [None for _ in range(N)]
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [[10**10] * N for _ in range(1<<N)]
    for i in range(N):
        dp[1<<i][i] = 0

    for s in range(1<<N):
        for k in range(N):
            if not(s & (1<<k)):
                continue
            for i in range(N):
                if s & (1<<i):
                    continue
                v1 = max(dp[s][k], B[k] - A[k] + A[i])
                s1 = s | (1<<i)
                dp[s1][i] = min(dp[s1][i], v1)

    ans = min(dp[(1<<N)-1])
    print(ans)

if __name__ == '__main__':
    main()