藏宝图

小王子很喜欢寻宝，有一天他得到了一幅藏宝图，图上标明的位置是非洲一个无人的沙漠，图上有一个N*M的矩阵，矩阵的每一个元素为一个整数。
小王子来到这片沙漠，他发现地图上标明-1的位置是流沙，如果不小心踩进去的话，就会陷阱去不能脱身。而其他地方都藏满了宝藏，而且地图上数字越大的地方，宝藏越丰富。
不一会儿，沙漠里出现了一只小狐狸，他告诉小王子，这片沙漠的宝藏具有再生的能力，只要你离开宝藏所在的位置，该位置又会生成和原来一样的宝藏。这片沙漠下面掩埋这一座古城，你进入这片沙漠后，必须在L步之内返回起点，不然沙漠将陷下去，摧毁古城。
小王子现在问聪明的你，他的初始位置是在地图的左上角，每次能走向与当前位置边相邻的上下左右的4个位置，走L步之内必须返回起点，能获得的最大宝藏总和，并且不能陷入流沙。
注：地图的左上角一定不为流沙。

第一行为一个整数T（1<=T<=5)表示测试用例的个数。
接下来每组测试数据格式为，第一行为三个正整数N,M,L (1<=N, M, L<=50)，分别表示地图的行、列数和最大步数。
接下来是一个N行M列的矩阵，每个元素用空格隔开。

对于每一个测试用例输出一个整数，代表小王子在L步之内返回起点所能获得的最大宝藏数。

1
5 5 5
10 10 10 10 -1
10 10 10 -1 10
3 3 3 -1 -1
2 2 2 -1 -1
2 2 2 -1 -1

50

中科院计算所第二届“斯伦贝谢”杯Debug大赛