记录编号	6264	评测结果	AAAAAAAAAA
题目名称	取数字问题	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.159 s
提交时间	2008-10-31 19:29:08	内存使用	6.22 MiB

#include <iostream>

#define MAXN 25
#define INF 9999999

using namespace std;

int n,m,ans,data[MAXN][MAXN];
bool f[MAXN][MAXN][10000];

/*void search(int x,int y,int now)
{
	if (x==n && y==m)
	{
		if (now>0)
			if (now<ans)
				ans=now;
		return;
	}
	if (x+1<=n)
		search(x+1,y,now+data[x+1][y]);
	if (y+1<=m)
		search(x,y+1,now+data[x][y+1]);
}*/

void run()
{
	int i,j,k;
	f[n][m][data[n][m]]=true;
	for (i=n;i>=1;i--)
		for (j=m;j>=1;j--)
			for (k=0;k<=10000;k++)
			{
				if (i+1<=n && k-data[i][j]>=0)
					if (f[i+1][j][k-data[i][j]])
						f[i][j][k]=true;
				if (j+1<=m && k-data[i][j]>=0)
					if (f[i][j+1][k-data[i][j]])
						f[i][j][k]=true;
			}
	ans=INF;
	for (k=0;k<=10000;k++)
		if (f[1][1][k])
			if (k-10*(n+m-1)>0 && abs(k-10*(n+m-1))<abs(ans))
				ans=k-10*(n+m-1);
	if (ans==INF)
		ans=-1;
}

void ini()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			cin>>data[i][j];
			data[i][j]+=10;
		}
}

int main()
{
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	ini();
	run();
	cout<<ans;
	return 0;
}