eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Это можно организовать

Это можно организовать

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Каждый год несколько университетов организуют межвузовские соревнования по программированию. 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_ib_i10000000) и s_i (1 s_i10000). Следующие n строк описывают временную матрицу, в которой i^{ая} строка содержит n целых чисел clean_ij (1 i n, 1 j n, 0 clean_ij10000000, clean_{ii }= 0).

Выходные данные

Для каждого теста вывести в отдельной строке его номер, начиная с 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
Источник 2013 ACM Southwestern Europe Regional Contest (SWERC), November 17, Problem B