Задачі
Это можно организовать
Это можно организовать
Каждый год несколько университетов организуют межвузовские соревнования по программированию. 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}, и ответ - наименьшее количество комнат, необходимое для аренды.
Вхідні дані #1
3 1 5 1 60 12 0 4 1 1 100 10 50 130 3 150 200 15 80 170 7 0 2 3 4 5 0 7 8 9 10 0 12 13 14 15 0 2 1 1 10 1 12 20 1 0 2 5 0
Вихідні дані #1
Case 1: 3 Case 2: 22 Case 3: 2