Каждый год несколько университетов организуют межвузовские соревнования по программированию. ACM ICPC Дакка проводит региональное соревнование каждый год в Дакке, где выбирается одна или две команды для участия на чемпионате мира ACM ICPC. Взяв это во внимание, MMR (Миссия Рахмана) решила открыть школу по программированию. В школе будут преподавать \textbf{n }дисциплин. Каждую дисциплину будут читать каждый день (иначе программисты забудут ДП когда будут учить вычислительную геометрию!). Вам будут заданы начальное \textbf{a_i} и конечное время \textbf{b_i} (включительно) каждого курса \textbf{i }(\textbf{1 }≤ \textbf{i }≤ \textbf{n}). Вам также будет известно количество студентов \textbf{s_i} (\textbf{1 }≤ \textbf{i }≤ \textbf{n}), зарегистрированных на этот курс. Ни один из студентов не зарегистрирован на два разных курса. MMR хочет арендовать несколько помещений в здании Башня Стража для работы этой школы. Каждая комната способна вместить до \textbf{m }студентов. Программисты (студенты) очень беспокойны и немножко грязные! Поэтому когда предмет \textbf{i} завершается в классе, следует потратить \textbf{clean_ij} времени для того чтобы убрать в нем, после чего можно начинать дисциплину \textbf{j} после дисциплины \textbf{i} в том же классе. Вы должны помочь MMR определить наименьшее количество классов, которое следует арендовать для работы школы программистов. \InputFile Начинается с количества тестов \textbf{t }(\textbf{t }≤ \textbf{100}). Каждый тест начинается двумя целыми числами: количеством курсов \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{100}) и вместимостью комнат \textbf{m }(\textbf{1 }≤ \textbf{m }≤ \textbf{10000}). Каждая из следующих \textbf{n }строк содержит три целых числа: начальное и конечное время курса \textbf{a_i}, \textbf{b_i} (\textbf{0 }≤ \textbf{a_i} ≤ \textbf{b_i} ≤ \textbf{10000000}) и \textbf{s_i} (\textbf{1 }≤ \textbf{s_i} ≤ \textbf{10000}). Следующие \textbf{n }строк описывают временную матрицу, в которой \textbf{i}^\{ая\} строка содержит \textbf{n }целых чисел \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 Для каждого теста вывести в отдельной строке его номер, начиная с \textbf{1}, и ответ - наименьшее количество комнат, необходимое для аренды.