题目描述

我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

输入格式

每组输入数据第一行包括三个整数，M、N和K，用空格隔开；表示花生田的大小为M*N（1<=M,N<=20），多多采花生的限定时间为K（0<=K<=1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i+1行的第j个整数Pij（0<=Pij<=500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。

输出格式

每组输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。

样例

样例 1

输入 # 1

6 7 21

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0



6 7 20

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0

输出 # 1

37



28