from bisect import bisect_left,bisect_right
N = int(input())
satisf = [tuple(map(int,input().split())) for _ in range(N)]
if N == 1:
    print(min(satisf[0]))
    exit()

left = [satisf[0][0],-satisf[0][1]]
for x,y in satisf[1:int(N//2)]:
    left = [l + x for l in left] + [l - y for l in left]
right = [satisf[N//2][0],-satisf[N//2][1]]
for x,y in satisf[int(N//2) + 1:]:
    right = [r + x for r in right] + [r - y for r in right]

right = list(set(right))
right.sort()
ans = 1<<30
for l in left:
    idx = bisect_left(right,-l)
    if idx == len(right):
        ans = min(ans,abs(right[idx - 1] + l))
    elif idx == 0:
        ans = min(ans,abs(right[0] + l))
    else:
        ans = min(ans,abs(right[idx - 1] + l),abs(right[idx] + l))
print(ans)