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())); } this.ShinamonoList = this.ShinamonoList.OrderByDescending(a => a.ValueA).ToList(); long ans = GetAns(0, Math.Max(this.ShinamonoList.Sum(a => a.ValueA), this.ShinamonoList.Sum(a => a.ValueB))); Console.WriteLine(ans); } private long GetAns(long min, long max) { if(max-min<=1) { if(IsValid(0, 0, 0, min)) { return min; } return max; } long mid = (max + min) / 2; if(IsValid(0,0,0,mid)) { return GetAns(min, mid); } return GetAns(mid, max); } private Dictionary>>> dic = new Dictionary>>>(); private bool IsValid(int idx, long subtotalA, long subtotalB, long diff) { if(idx >= this.ShinamonoList.Count) { return Math.Abs(subtotalA - subtotalB) <= diff; } long newSubtotalB = subtotalB + this.ShinamonoList.Skip(idx).Sum(a => a.ValueB); if (subtotalA - newSubtotalB > diff) { return false; } long newSubtotalA = subtotalA + this.ShinamonoList.Skip(idx).Sum(a => a.ValueA); if(subtotalB - newSubtotalA>diff) { return false; } if (Math.Abs(subtotalA - newSubtotalB) <= diff) { return true; } if (Math.Abs(newSubtotalA - subtotalB) <= diff) { return true; } 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)) { dic[idx][subtotalA].Add(subtotalB, new Dictionary()); } if(dic[idx][subtotalA][subtotalB].ContainsKey(diff)) { return dic[idx][subtotalA][subtotalB][diff]; } bool ans = false; if(IsValid(idx + 1, subtotalA + this.ShinamonoList[idx].ValueA, subtotalB, diff)) { ans = true; } else if( IsValid(idx + 1, subtotalA, subtotalB + this.ShinamonoList[idx].ValueB, diff)) { ans = true; } dic[idx][subtotalA][subtotalB][diff] = 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(); } }