Every year, several universities arrange inter-university national programming contests. ACM ICPC Dhaka site regional competition is held every year in Dhaka and one or two teams are chosen for ACM ICPC World Finals. By observing these, MMR (Mission Maker Rahman) has made a plan to open a programming school. In that school \textbf{n }courses are taught. Each course is taught every day (otherwise, programmers may forget DP while learning computational geometry!). You will be given the starting time \textbf{a_i} and finishing time \textbf{b_i} (inclusive) of each course \textbf{i }(\textbf{1 }≤ \textbf{i }≤ \textbf{n}). You will be also given the number of students registered for each course \textbf{s_i} (\textbf{1 }≤ \textbf{i }≤ \textbf{n}). You can safely assume no student has registered to two different courses. MMR wants to hire some rooms of a building, named Sentinel Tower, for running that school. Each room of Sentinel Tower has a capacity to hold as much as \textbf{m} students. The programmers (students) are very restless and a little bit filthy! As a result, when course \textbf{i} is taken in a class room, after the class is finished, it takes \textbf{clean_ij} time to clean the room to make it tidy for starting teaching course \textbf{j} immediately just after course \textbf{i} in the same room. Your job is to help MMR to decide the minimum number of rooms need to be hired to run the programming school. \InputFile Starts with the number of test cases \textbf{t }(\textbf{t }≤ \textbf{100}). Each case starts with two integers \textbf{ n} (\textbf{1 }≤ \textbf{n }≤ \textbf{100}), number of courses and \textbf{m }(\textbf{1 }≤ \textbf{m }≤ \textbf{10000}), capacity of a room. Next \textbf{n }lines will contain three integers \textbf{a_i}, \textbf{b_i} (\textbf{0 }≤ \textbf{a_i} ≤ \textbf{b_i} ≤ \textbf{10000000}) and \textbf{s_i} (\textbf{1 }≤ \textbf{s_i} ≤ \textbf{10000}), starting and finishing time of a course. Next \textbf{n }lines will contain the clean time matrix, where the \textbf{i}^th row will contain \textbf{n }integers \textbf{clean_ij} (\textbf{1 }≤ \textbf{i }≤ \textbf{n}, \textbf{1 }≤ \textbf{j }≤ \textbf{n}, \textbf{0 }≤ \textbf{clean_ij} ≤ \textbf{10000000}, \textbf{clean_\{ii \}}= \textbf{0}). \OutputFile For each case, print the test case number, starting from \textbf{1}, and the answer, minimum number of rooms needed to be hired.