# coding: utf-8 # Your code here! # -*- coding: utf-8 -*- """ Created on Tue Aug 19 11:12:16 2025 @author: Maiku """ N = int(input()) data = [list(map(int, input().split())) for _ in range(N)] INF = 1 << 60 dp = [[INF for v in range(N)] for s in range(1<> v) & 1 or dp[s][v]==INF: continue a, b = data[v] for nx in range(N): if (s >> nx) & 1: continue c, d = data[nx] ns = s | (1 << nx) dp[ns][nx] = min(dp[ns][nx], max(dp[s][v], c + b - a)) #print(dp) print(min(dp[-1]))