using System; using System.Collections.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray(); ItemCount = inpt[0]; int inputCount = inpt[1]; for(int i=0; iint.Parse(a)).ToArray(); if(!pointDic.ContainsKey(inpt[1])) { pointDic.Add(inpt[1], new Dictionary()); } pointDic[inpt[1]].Add(inpt[0], inpt[2]); } long ans = this.GetAns(0, this.ItemCount); Console.WriteLine(ans); } private int ItemCount = 0; private Dictionary dic = new Dictionary(); private long GetAns(int flag, int remain) { if(dic.ContainsKey(flag)) { return dic[flag]; } if(remain == 0) { return 0; } long ans = 0; for(int i=0; i> pointDic = new Dictionary>(); public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 4 9 0 1 1 0 2 2 0 3 3 1 2 4 1 3 5 2 3 6 3 2 100 2 1 100 1 0 100 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } } static void Main() { Program prg = new Program(); prg.Proc(); } }