#include #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) using namespace std; typedef long long ll; constexpr int INF = 1e9 + 7; class max_flow { struct edge_t { int to; ll cap; int rev; }; int v; vector > g; vector iter, level; public: max_flow(int v_) : v(v_), g(v) { } void add_edge(int from, int to, ll cap) { g[from].push_back((edge_t) { to, cap, (int)g[to].size() }); g[to].push_back((edge_t) { from, 0ll, (int)g[from].size() - 1 }); } private: void bfs(int src) { level.assign(v, -1); queue q; level[src] = 0; q.push(src); while (not q.empty()) { int x = q.front(); q.pop(); for (auto & e : g[x]) { if (e.cap > 0 and level[e.to] < 0) { level[e.to] = level[x] + 1; q.push(e.to); } } } } ll dfs(int x, int dst, ll flow) { if (x == dst) return flow; for (int & i = iter[x]; i < (int)g[x].size(); ++ i) { edge_t & e = g[x][i]; if (e.cap > 0 and level[x] < level[e.to]) { ll d = dfs(e.to, dst, min(flow, e.cap)); if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0; } public: ll run_destructive(int src, int dst) { ll flow = 0; bfs(src); while (level[dst] >= 0) { iter.assign(v, 0); while (true) { ll delta = dfs(src, dst, INF); if (delta <= 0) break; flow += delta; } bfs(src); } return flow; } }; int solve(int n, vector a, vector b) { int sum_a = accumulate(ALL(a), 0); int sum_b = accumulate(ALL(b), 0); if (sum_a > sum_b) { a.swap(b); swap(sum_a, sum_b); } max_flow g(2 * n); const int src = n - 1; const int dst = 2 * n - 1; REP (i, n - 1) { g.add_edge(src, i, a[i]); REP (j, n - 1) if (j != i) { g.add_edge(i, n + j, min(a[i], b[j])); } g.add_edge(n + i, dst, b[i]); } int l = sum_b - g.run_destructive(src, dst); int r = sum_b; return r - l + 1; } int main() { int n; cin >> n; vector a(n - 1), b(n - 1); REP (i, n - 1) { cin >> a[i] >> b[i]; } cout << solve(n, a, b) << endl; return 0; }