#include using namespace std; signed main() { ios::sync_with_stdio(false); int N; cin >> N; vector A(N), B(N); for (int i = 0; i < N; ++i) { cin >> A[i] >> B[i]; } vector> dp(1 << N, vector(N, 0x3f3f3f3f)); for (int i = 0; i < N; ++i) dp[1 << i][i] = 0; for (int s = 1; s + 1 < 1 << N; ++s) { for (int i = 0; i < N; ++i) { if (~s >> i & 1) continue; for (int j = 0; j < N; ++j) { if (i == j) continue; if (s >> j & 1) continue; dp[s | 1 << j][j] = min(dp[s | 1 << j][j], max(dp[s][i], B[i] - A[i] + A[j])); } } } cout << *min_element(dp.back().begin(), dp.back().end()) << endl; return 0; }