using System; using System.Collections; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.GetInt(); int itemCount = inpt[0]; this.MaxTotalPrice = inpt[1]; this.PriceList = new int[itemCount + 1]; List indexList = new List(); for(int i=1; i<=itemCount; i++) { this.PriceList[i] = int.Parse(Reader.ReadLine()); indexList.Add(i); } List ans = this.GetAns(1, MaxTotalPrice); if(ans == null) { Console.WriteLine("-1"); } else { foreach (string item in ans) { Console.WriteLine(item.Trim()); } } } private Dictionary>> dic = new Dictionary>>(); private List GetAns(int idx, int remain) { if(!dic.ContainsKey(idx)) { dic.Add(idx, new Dictionary>()); } if(dic[idx].ContainsKey(remain)) { return dic[idx][remain]; } if(remain == 0) { List ret = new List(); ret.Add(string.Empty); return ret; } if(remain < 0) { return null; } if(idx >= this.PriceList.Length) { return null; } List ans = new List(); List subAns = null; if(this.PriceList[idx] <= remain) { subAns = this.GetAns(idx + 1, remain - this.PriceList[idx]); if(subAns != null) { foreach (string item in subAns) { ans.Add(idx + " " + item); } } } subAns = this.GetAns(idx + 1, remain); if(subAns != null) { ans.AddRange(subAns); } if(ans.Count == 0) { ans = null; } this.dic[idx].Add(remain, ans); return ans; } private int MaxTotalPrice = 0; private int[] PriceList; public class Reader { private static String InitText = @" 3 220 180 220 280 "; private static System.IO.StringReader sr = null; public static bool IsDebug = true; public static string ReadLine() { if(IsDebug) { if(sr == null) { sr = new System.IO.StringReader(InitText.Trim()); } return sr.ReadLine(); } else { return Console.ReadLine(); } } public static int[] GetInt(char delimiter = ' ') { string[] inpt = ReadLine().Split(delimiter); int[] ret = new int[inpt.Length]; for(int i=0; i