P16893 [GKS 2022 #G] Walktober

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 为实现目标所需的最小额外步数总和。

在样例中，比赛持续 $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 完成