题目描述

John 参加了一项名为 Walktober 的年度步行比赛。比赛总共持续 $N$ 天，并记录所有参赛者在 $N$ 天中的每日步数。每位参赛者将被分配一个唯一的 ID，范围从 $1$ 到 $M$，其中 $M$ 是注册参赛者的总数。系统维护一个全局排行榜，记录每位参赛者每天的步数。

John 决心在今年赢得 Walktober，他的目标是成为每一天中步数最多的参赛者。他也参加了去年的比赛，因此他想知道自己在实现目标时还差了多少步。给定去年的排行榜，请计算为了使自己每天都能达到最高步数，John 需要在去年成绩的基础上最少增加多少步。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含 $3$ 个整数 $M$、$N$ 和 $P$，分别表示参赛者总数、比赛持续的总天数以及 John 在去年的参赛者 ID。

接下来的 $M$ 行描述去年的排行榜，每行包含 $N$ 个整数。

第 $i$ 行的第 $j$ 个整数表示 ID 为 $i$ 的参赛者在比赛第 $j$ 天的步数 $S_{i,j}$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 John 为实现目标所需的最小额外步数总和。

1
2 3 1
1000 2000 3000
1500 1500 3000

Case #1: 500

2
3 2 3
1000 2000
1500 4000
500 4000
3 3 2
1000 2000 1000
1500 2000 1000
500 4000 1500

Case #1: 1000
Case #2: 2500

提示

在样例中，比赛持续 $3$ 天，John 的参赛者 ID 为 $1$。在第 $1$ 天，由于其他参赛者步数更多，John 需要增加 $500$ 步。其余几天 John 的步数已经是最高，因此不需要额外步数。所以，他总共需要增加 $500$ 步才能实现目标。

在附加样例 #1 中，比赛持续 $2$ 天，John 的 ID 为 $3$。他在第 $1$ 天需要增加 $1000$ 步，第 $2$ 天不需要增加步数，总计 $1000$ 步。

在附加样例 #2 中，比赛持续 $3$ 天，John 的 ID 为 $2$。他在第 $1$ 天不需要增加步数，第 $2$ 天需要增加 $2000$ 步，第 $3$ 天需要增加 $500$ 步，总计 $2500$ 步。

限制条件

$1 \le T \le 100$。

$1 \le N \le 31$。

对于所有 $i$ 和 $j$，$1 \le S_{i,j} \le 60000$。

$1 \le P \le M$。

测试集 1

$M = 2$。

测试集 2

$2 \le M \le 1000$。

翻译由 DeepSeek V4 Pro 完成