using System; using System.IO; using System.Linq; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { int itemCount = int.Parse(Reader.ReadLine()); for (int i = 0; i < itemCount; i++) { this.ShinamonoList.Add(new Shinamono(Reader.ReadLine())); } long ans = GetAns(0, 0, 0); Console.WriteLine(ans); } private Dictionary>> dic = new Dictionary>>(); private long GetAns(int idx, long subtotalA, long subtotalB) { if(idx>=this.ShinamonoList.Count) { return Math.Abs(subtotalA - subtotalB); } if(!dic.ContainsKey(idx)) { dic.Add(idx, new Dictionary>()); } if(!dic[idx].ContainsKey(subtotalA)) { dic[idx].Add(subtotalA, new Dictionary()); } if(dic[idx][subtotalA].ContainsKey(subtotalB)) { return dic[idx][subtotalA][subtotalB]; } long ans = long.MaxValue; ans = Math.Min(ans, GetAns(idx + 1, subtotalA + this.ShinamonoList[idx].ValueA, subtotalB)); ans = Math.Min(ans, GetAns(idx + 1, subtotalA, subtotalB + ShinamonoList[idx].ValueB)); dic[idx][subtotalA][subtotalB] = ans; return ans; } private List ShinamonoList = new List(); private class Shinamono { public long ValueA; public long ValueB; public Shinamono(string init) { long[] tmp = init.Split(' ').Select(a => long.Parse(a)).ToArray(); this.ValueA = tmp[0]; this.ValueB = tmp[1]; } } public class Reader { private static StringReader sr; public static bool IsDebug = false; public static string ReadLine() { if (IsDebug) { if (sr == null) { sr = new StringReader(InputText.Trim()); } return sr.ReadLine(); } else { return Console.ReadLine(); } } private static string InputText = @" 1 10 15 "; } public static void Main(string[] args) { #if DEBUG Reader.IsDebug = true; #endif Program prg = new Program(); prg.Proc(); } }