Це можна організувати
Кожного року кілька університетів організовують міжвузівські змагання з програмування. 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, і відповідь - найменшу кількість кімнат, необхідну для оренди.