using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Text; using System.Text.RegularExpressions; using System.Linq; using System.IO; class Program { static void Main() { new Magatro().Solve(); } } class Magatro { private int N; private int[] A, B; private List a = new List(), b = new List(); private long ans = long.MaxValue; private void Scan() { N = int.Parse(Console.ReadLine()); A = new int[N]; B = new int[N]; for (int i = 0; i < N; i++) { var line = Console.ReadLine().Split(' '); A[i] = int.Parse(line[0]); B[i] = int.Parse(line[1]); } } private void DFS(long aa, long bb, int left, int right, List t) { if (left == right) { t.Add(aa - bb); return; } DFS(aa + A[left], bb, left + 1, right, t); DFS(aa, bb + B[left], left + 1, right, t); } public void Solve() { Scan(); DFS(0, 0, 0, N / 2, a); DFS(0, 0, N / 2, N, b); b.Sort(); long ans = long.MaxValue; foreach (long l in a) { int left = 0, right = b.Count; while (right - left > 1) { int mid = (left + right) / 2; if (l + b[mid] > 0) { right = mid; } else { left = mid; } } ans = Math.Min(l + b[right], ans); left = -1; right = b.Count-1; while (right - left > 1) { int mid = (left + right) / 2; if (l + b[mid] >= 0) { right = mid; } else { left = mid; } } ans = Math.Min(l + b[right], ans); } Console.WriteLine(ans); } }