강의실 배치는 가능하다

매년 여러 대학이 전국 규모의 프로그래밍 대회를 연다. 다카에서도 매년 ICPC 지역 대회가 열리고, 여기서 한두 팀이 ICPC 월드 파이널에 나간다.

이 대회를 지켜본 MMR(Mission Maker Rahman)은 프로그래밍 학교를 열기로 했다. 학교에서는 코스 $N$개를 가르치고, 모든 코스는 매일 열린다. 계산 기하를 배우는 동안 다이나믹 프로그래밍을 잊어버리면 안 되기 때문이다. 코스 $i$는 시각 $A_i$에 시작해서 시각 $B_i$에 끝나고, 양쪽 끝 시각도 수업 시간에 들어간다. 코스 $i$의 수강생은 $S_i$명이고, 두 코스를 같이 듣는 학생은 없다.

MMR은 Sentinel Tower라는 건물의 방 몇 개를 빌려 학교를 운영하려 한다. 방 하나에는 학생이 최대 $M$명까지 들어간다. 그래서 코스 $i$는 같은 시간에 방 $\lceil S_i / M \rceil$개를 쓰고, 각 방에서 같은 수업을 따로 진행한다.

프로그래머는 잠시도 가만히 있지 못하고 뒷정리에도 관심이 없다. 그래서 어떤 방에서 코스 $i$ 수업이 끝나면, 같은 방에서 코스 $j$ 수업을 시작하기 전에 청소하는 데 $\text{clean}_{ij}$만큼의 시간이 걸린다. 정리하면 같은 방에서 코스 $i$ 바로 다음에 코스 $j$를 진행할 수 있는 조건은 $B_i + \text{clean}_{ij} < A_j$이다.

모든 코스가 매일 같은 시각에 반복되므로 하루 일정만 계획하면 된다. MMR이 빌려야 하는 방의 최소 개수를 구하자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 100$)

각 테스트 케이스의 첫째 줄에는 코스의 개수 $N$과 방 하나의 정원 $M$이 주어진다. ($1 \le N \le 100$, $1 \le M \le 10000$)

다음 $N$개 줄에는 코스 $i$의 시작 시각 $A_i$, 종료 시각 $B_i$, 수강생 수 $S_i$가 주어진다. ($0 \le A_i \le B_i \le 10^7$, $1 \le S_i \le 10000$)

그다음 $N$개 줄에는 청소 시간 행렬이 주어진다. $i$번째 줄의 $j$번째 정수가 $\text{clean}_{ij}$이다. ($0 \le \text{clean}_{ij} \le 10^7$, $\text{clean}_{ii} = 0$)

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 빌려야 하는 방의 최소 개수이다.