每年，几所大学都会举办校际全国程序设计竞赛。ACM ICPC 达卡赛区区域赛每年在达卡举行，并选出一到两支队伍参加 ACM ICPC 全球总决赛。

受此启发，MMR (Mission Maker Rahman) 计划开办一所编程学校。学校里开设了 $N$ 门课程。每门课程每天都会教授（否则，程序员们在学习计算几何时可能会忘记动态规划！）。你将获得每门课程 $i$ ($1 \le i \le N$) 的开始时间 $A_i$ 和结束时间 $B_i$（包含边界）。你还将获得每门课程注册的学生人数 $S_i$ ($1 \le i \le N$)。你可以放心地假设没有学生注册了两门不同的课程。MMR 想要租用名为 Sentinel Tower 的大楼中的一些房间来开办这所学校。Sentinel Tower 的每个房间最多可容纳 $M$ 名学生。程序员（学生）非常不安分，而且有点邋遢！因此，当课程 $i$ 在某个教室上完后，如果紧接着在同一个房间教授课程 $j$，则需要花费 $\text{clean}_{ij}$ 的时间来打扫房间，使其变得整洁。

你的任务是帮助 MMR 决定开办这所编程学校所需租用的最少房间数。

输入格式

输入的第一行包含一个整数 $T$ ($T \le 100$)，表示测试用例的数量。每个测试用例的第一行包含两个整数 $N$ ($1 \le N \le 100$)，表示课程数量，以及 $M$ ($1 \le M \le 10000$)，表示每个房间的容量。接下来的 $N$ 行，每行包含三个整数 $A_i, B_i$ ($0 \le A_i \le B_i \le 10000000$) 和 $S_i$ ($1 \le S_i \le 10000$)，分别表示课程的开始时间和结束时间。接下来的 $N$ 行包含清理时间矩阵，其中第 $i$ 行包含 $N$ 个整数 $\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 开始）以及所需的最小房间数。

样例

样例输入 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

样例输出 1

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