using System; using System.IO; using System.Linq; using System.Collections.Generic; public class Program { public void Proc() { int inputCount = int.Parse(Reader.ReadLine()); for (int i = 0; i < inputCount; i++) { int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray(); this.NimotsuList.Add(new Nimotu(inpt[0], inpt[1])); } int target = int.Parse(Reader.ReadLine()); this.NimotsuList = this.NimotsuList.OrderBy(a => a.Value).ToList(); long tmp1 = GetAns(0, target); long tmp2 = 1; if(tmp1 == 0) { long tmp = GetAns3(0, target); if(tmp == target || tmp <= 0) { tmp1 = 1; tmp2 = this.NimotsuList.Min(a => a.Size - 1); } else { tmp1 = GetAns(0, tmp); tmp2 = GetAns2(0, tmp); } } else { long tmp = GetAns4(0, target); if(tmp == target || tmp < 0) { tmp2 = NimotsuList.Sum(a => a.Size); } else { tmp2 = GetAns(0, tmp) - 1; } } Console.WriteLine(tmp1); if(tmp2 == this.NimotsuList.Sum(a=>a.Size)) { Console.WriteLine("inf"); } else { Console.WriteLine(tmp2); } } private Dictionary> dic = new Dictionary>(); private Dictionary> dic2 = new Dictionary>(); private Dictionary> dic3 = new Dictionary>(); private Dictionary> dic4 = new Dictionary>(); private long GetAns4(int idx, long remain) { if (remain < 0) { return 0; } if (idx >= this.NimotsuList.Count) { if (remain < 0) { return 0; } return -1; } if (!dic4.ContainsKey(idx)) { dic4.Add(idx, new Dictionary()); } if (dic4[idx].ContainsKey(remain)) { return dic4[idx][remain]; } long ans = long.MaxValue; long tmp; tmp = GetAns4(idx + 1, remain - NimotsuList[idx].Value); if (tmp >= 0) { ans = Math.Min(ans, tmp + NimotsuList[idx].Value); } tmp = GetAns4(idx + 1, remain); if (tmp >= 0) { ans = Math.Min(ans, tmp); } if(ans == long.MaxValue) { ans = -1; } dic4[idx][remain] = ans; return ans; } private long GetAns3(int idx, long remain) { if (remain <= 0) { return -1; } if (idx >= this.NimotsuList.Count) { if (remain <= 0) { return -1; } return 0; } if (!dic3.ContainsKey(idx)) { dic3.Add(idx, new Dictionary()); } if (dic3[idx].ContainsKey(remain)) { return dic3[idx][remain]; } long ans = 0; long tmp; if (this.NimotsuList[idx].Value < remain) { tmp = GetAns3(idx + 1, remain - NimotsuList[idx].Value); if (tmp >= 0) { ans = Math.Max(ans, tmp + NimotsuList[idx].Value); } } tmp = GetAns3(idx + 1, remain); if (tmp >= 0) { ans = Math.Max(ans, tmp); } dic3[idx][remain] = ans; return ans; } private long GetAns2(int idx, long remain) { if (remain == 0) { return 0; } if (idx >= this.NimotsuList.Count) { return -1; } if (!dic2.ContainsKey(idx)) { dic2.Add(idx, new Dictionary()); } if (dic2[idx].ContainsKey(remain)) { return dic2[idx][remain]; } long ans = 0; long tmp; if (this.NimotsuList[idx].Value <= remain) { tmp = GetAns2(idx + 1, remain - NimotsuList[idx].Value); if (tmp >= 0) { ans = Math.Max(ans, tmp + NimotsuList[idx].Size); } } tmp = GetAns2(idx + 1, remain); if (tmp >= 0) { ans = Math.Max(ans, tmp); } dic2[idx][remain] = ans; return ans; } private long GetAns(int idx, long remain) { if(remain == 0) { return 0; } if (idx >= this.NimotsuList.Count) { return -1; } if(!dic.ContainsKey(idx)) { dic.Add(idx, new Dictionary()); } if(dic[idx].ContainsKey(remain)) { return dic[idx][remain]; } long ans = long.MaxValue; long tmp; if(this.NimotsuList[idx].Value <= remain) { tmp = GetAns(idx + 1, remain - NimotsuList[idx].Value); if(tmp >= 0) { ans = Math.Min(ans, tmp + NimotsuList[idx].Size); } } tmp = GetAns(idx + 1, remain); if (tmp >= 0) { ans = Math.Min(ans, tmp); } if(ans == long.MaxValue) { ans = -1; } dic[idx][remain] = ans; return ans; } private List NimotsuList = new List(); private class Nimotu { public long Value; public long Size; public Nimotu(int val, int size) { this.Value = val; this.Size = size; } } 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 = @" 2 33 4 114 514 147 "; } public static void Main(string[] args) { #if DEBUG Reader.IsDebug = true; #endif Program prg = new Program(); prg.Proc(); } }