1342: 宝石！（必做）

在神秘的地下矿洞中，分布着由 n×m 个矿格组成的矩形区域。探险者从矿洞底部出发，想要收集尽可能多的宝石，但他需要将宝石平均分给 K 个伙伴，因此收集的宝石总数必须是 K+1 的倍数。探险者每次只能向左上角或右上角的矿格移动（即从 (i,j) 只能走到 (i-1,j-1) 或 (i-1,j+1)），且可以从底部任意矿格作为起点。请计算他能收集的最大宝石数量，若不存在符合条件的路径则输出 - 1。

第一行输入一个整数 T，表示测试数据组数。 每组数据第一行包含三个整数 n, m, K（0 < n,m ≤ 100，0 ≤ K ≤ 10），分别表示矿洞的行数、列数和伙伴数量。 接下来 n 行，每行包含 m 个数字（0-9），表示每个矿格的宝石数量（数字无间隔）。

对每组数据，输出一行整数，表示探险者能收集的最大宝石数（需为 K+1 的倍数），若无符合条件的路径则输出 - 1。

3
3 3 0
123
456
789
3 3 1
123
456
789
2 2 10
98
75

17
16
-1