It Can Be Arranged

Every year several universities host national programming contests. Dhaka holds an ICPC regional contest every year, and one or two teams from it go to the ICPC World Finals.

After watching those contests, MMR (Mission Maker Rahman) decided to open a programming school. The school teaches $N$ courses, and every course meets every day, because a programmer must not forget dynamic programming while learning computational geometry. Course $i$ starts at time $A_i$ and finishes at time $B_i$, and both endpoints count as class time. Course $i$ has $S_i$ registered students, and no student is registered for two courses.

MMR wants to hire rooms in a building called Sentinel Tower. One room holds at most $M$ students, so course $i$ occupies $\lceil S_i / M \rceil$ rooms at the same time and runs the same class separately in each of them.

Programmers are restless and they leave a mess. Once course $i$ finishes in a room, cleaning that room before course $j$ starts there takes $\text{clean}_{ij}$ time. So course $j$ can follow course $i$ directly in the same room only when $B_i + \text{clean}_{ij} < A_j$.

Every course repeats at the same time each day, so you plan a single day. Find the minimum number of rooms MMR has to hire.

The first line has the number of test cases $T$. ($T \le 100$)

The first line of each test case has the number of courses $N$ and the capacity of one room $M$. ($1 \le N \le 100$, $1 \le M \le 10000$)

Each of the next $N$ lines has the start time $A_i$, the finish time $B_i$, and the number of registered students $S_i$ of course $i$. ($0 \le A_i \le B_i \le 10^7$, $1 \le S_i \le 10000$)

Each of the next $N$ lines has one row of the cleaning time matrix. The $j$-th integer of the $i$-th row is $\text{clean}_{ij}$. ($0 \le \text{clean}_{ij} \le 10^7$, $\text{clean}_{ii} = 0$)

For each test case print one line in the form Case x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of rooms to hire.