问题 6339 --小Y收集糖果

6339: 小Y收集糖果★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 4
[提交][状态][命题人:]

题目描述

小Y在游园会上参加收集糖果的活动,整个活动场地可以抽象为一个 n * m 的方阵,每个位置上存在0 - 9 颗糖果,小Y初始在左上角 (1, 1),小Y可以往下走或往右走,终点在 (n, m)

由于有 k 个好兄弟在等待小Y,因此为了不让好兄弟们起冲突,小Y希望最后获得的糖果能够被 k + 1 个人平分,同时尽可能的多,请问小Y最多可以拿到多少个糖果。

需要注意,如果小k路过某一格,他必须拿上这个格内的所有糖果。

输入

第一行三个整数 n, m, k 分别表示场地的行数、列数和兄弟的人数。

随后跟着 n 行,每行 m 个整数,表示每个位置具有的糖果数量。

其中n,m<=100,k<=10

输出

一个整数,代表小Y在满足糖果能被 k + 1 整除的情况下的最多糖果数。如果不存在这样的答案,输出-1。
样例输入
Copy
3 3 1
1 2 3
4 5 6 
7 8 8
样例输出
Copy
28

提示

来源

[提交][状态]