### 问题描述 在未来的某一天，地球联邦收到了来自遥远星系的一封求援信。为了援救被困在遥远星球上的居民，地球联邦决定派出一支由 $K$ 名宇航员和一个导师组成的救援队伍。他们会乘坐宇宙飞船前往遥远星系，然后入住星际驿站进行最后的准备。 星际驿站内部是一个 $N \times M$ 的矩阵布局，共有 $N \times M$ 个房间，每个房间 $(i, j)$ 可以容纳 $A(i, j)$ 人。房间 $(i_1, j_1)$ 和房间 $(i_2, j_2)$ 之间的距离为 $\max(|i_1 - i_2|, |j_1 - j_2|)$，其中 $|X|$ 表示 $X$ 的绝对值。 为了确保行动的顺利进行，需要安排导师和宇航员们的住宿，使得导师和最远的宇航员之间的距离尽可能小。注意，导师和宇航员可以住在同一个房间。 你的任务是找到导师和最远宇航员之间的最小距离。如果星际驿站的总容量小于 $K + 1$，则打印 $-1$。 ### 输入格式 输入的第一行包含一个单独的整数 $T$ ，表示测试用例的数量。 每个测试用例的第一行包含三个空格分隔的整数 $N$，$M$ 和 $K$ ——驿站的行数、列数和宇航员的数量。 接下来的 $N$ 行，每行包含 $M$ 个空格分隔的整数，表示每个房间的容量。 ### 输出格式 对于每个测试用例，输出在新行中，导师和最远宇航员之间的最小距离。 如果星际驿站的总容量小于 $K + 1$，则打印 $-1$。 ### 样例输入 ```text 4 1 7 5 2 1 0 1 3 0 1 2 4 3 1 0 4 0 0 2 0 3 2 2 7 1 0 4 1 3 2 3 0 2 1 0 1 0 ``` ### 样例输出 ```text 3 0 -1 1 ``` ### 说明 测试用例 1：导师可以待在房间 $(1, 2)$，两个宇航员在房间 $(1, 1)$，一个宇航员在房间 $(1, 4)$ 和两个宇航员在房间 $(1, 5)$。最远的宇航员房间是 $(1, 5)$，距离为 $3$。没有其他的安排可以使得距离小于 $3$。 测试用例 $2$：导师和所有 $3$ 个宇航员可以待在房间 $(1, 3)$。因此，距离是 0。 测试用例 3：星际驿站的容量不足。 ### 评测数据范围 $1 \leq T \leq 500$。 $1 \leq N, M \leq 10^6$。 $1 \leq K \leq 10^9$。 $0 \leq A(i, j) \leq 10^5$。 对所有测试用例，$N \times M$ 的总和不超过 $10^6$。