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