题目描述
【问题背景】
空闲之时,下局棋,未尝不好……
【问题描述】
一场恶战,浪子最后只剩下了一个卒。而对方,还有……这场战斗以失败告终。不过浪子突发其想,把一个卒放在一张N*M的棋盘上。每个格子都有个分值。卒每移动到一个格子,就要减少那个格子上的分值(先减再走)。假设卒刚开始只有T分,求出卒从左上角走到右下角所剩的最大分值。(为了简化问题,卒只能向左右或向下移动,最左端与最右端是不相连的。即卒在最某行最左端时,只能向右或向下移动;卒在最某行最右端时,只能向左或向下移动。)
当此时,某位同学把浪子喊去开唰(就是拿很多题目来……),浪子只好发到网上来求助。
输入格式
第1行,三个数:N,M,T(1≤N,M≤100,1≤T≤1000)。
接下来N行,每行M个数。第I行的第J个数A[I,J]表示这格的分值(0≤A[I,J]≤10)
输出格式
若卒走到右下角时,所剩的最大分值为正,那么输出所剩的最大分值。反之,则输出“DONOT HAVE MORE”(不包括引号)
样例输入
样例输出