Це можна організувати#7217
Кожного року кілька університетів організовують міжвузівські змагання з програмування. ACM ICPC Дака проводить регіональне змагання щороку в Даці, де обирається одна або дві команди для участі у чемпіонаті світу ACM ICPC.
Зважаючи на це, MMR (Місія Рахмана) вирішила відкрити школу програмування. У школі викладатимуть дисциплін. Кожну дисципліну проводитимуть щодня (інакше програмісти забудуть ДП, коли вивчатимуть обчислювальну геометрію!). Вам надано початковий a_i та кінцевий час b_i (включно) для кожного курсу (1 \le i \le n). Також відома кількість студентів s_i (1 \le i \le n), зареєстрованих на цей курс. Жоден зі студентів не зареєстрований на два різних курси. MMR планує орендувати кілька приміщень у будівлі Вежа Вартового для роботи цієї школи. Кожна кімната може вмістити до студентів. Програмісти (студенти) дуже неспокійні і трохи неохайні! Тому, коли предмет завершується в класі, потрібно витратити \text{clean}_{ij} часу на прибирання, перш ніж можна буде розпочати дисципліну після дисципліни в тому ж класі.
Ви повинні допомогти MMR визначити найменшу кількість класів, яку слід орендувати для роботи школи програмістів.
Спочатку йде кількість тестів (t \le 100). Кожен тест починається з двох цілих чисел: кількості курсів (1 \le n \le 100) і місткості кімнат (1 \le m \le 10000). Кожен з наступних рядків містить три цілі числа: початковий і кінцевий час курсу a_i, b_i (0 \le a_i \le b_i \le 10000000) та s_i (1 \le s_i \le 10000). Наступні рядків описують часову матрицю, де -й рядок містить цілих чисел \text{clean}_{ij} (1 \le i \le n, 1 \le j \le n, 0 \le \text{clean}_{ij} \le 10000000, \text{clean}_{ii} = 0).
Для кожного тесту виведіть в окремому рядку його номер, починаючи з , і відповідь - найменшу кількість кімнат, необхідну для оренди.
Приклад 1