Every year, several universities arrange interuniversity
national programming contests. ACM ICPC Dhaka site regional
competition is held every year in Dhaka and one or two teams
are chosen for ACM ICPC World Finals.
By observing these, MMR (Mission Maker Rahman) has made a
plan to open a programming school. In that school, $N$ courses are taught. Each course is
taught every day (otherwise, programmers may forget DP while
learning computational geometry!). You will be given the
starting time $A_ i$ and
finishing time $B_ i$
(inclusive) of each course $i$ ($1
\leq i \leq N$). You will be also given the number of
students registered for each course, $S_ i$ ($1 \leq i \leq N$). You can safely
assume no student has registered to two different courses. MMR
wants to hire some rooms of a building, named Sentinel
Tower, for running that school. Each room of Sentinel
Tower has a capacity to hold as much as $M$ students. The programmers
(students) are very restless and a little bit filthy! As a
result, when $\texttt{course}_
i$ is taken in a class room, after the class is
finished, it takes $\texttt{clean}_{ij}$ time to clean
the room to make it tidy for starting teaching $\texttt{course}_ j$ immediately just
after $\texttt{course}_ i$
in the same room.
Your job is to help MMR to decide the minimum number of
rooms need to be hired to run the programming school.
Input
Input starts with an integer $T$ ($T
\leq 100$) denoting the number of test cases. Each case
starts with two integers $N$ ($1
\leq N \leq 100$), number of courses and $M$ ($1
\leq M \leq 10\, 000$), capacity of a room. Next
$N$ lines will contain
three integers $A_ i$,
$B_ i$ ($0 \leq A_ i \leq B_ i \leq 10\, 000\,
000$) and $S_ i$
($1 \leq S_ i \leq 10\,
000$), starting and finishing time of a course. Next
$N$ lines will contain the
clean time matrix, where the $i$th row will contain $N$ integers $\texttt{clean}_{ij}$ ($1 \leq i \leq N$, $1 \leq j \leq N$, $0 \leq \texttt{clean}_{ij} \leq 10\, 000\,
000$, $\texttt{clean}_{ii}
= 0$).
Output
For each case, print the test case number, starting from 1,
and the answer, minimum number of rooms needed to be hired.
Sample Input 1 
Sample Output 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

Case 1: 3
Case 2: 22
Case 3: 2
