问题 3847 --大神洗澡

3847: 大神洗澡

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][56kb]

题目描述

大神戚袁远现在要洗澡。他已经30年没洗澡了。所以这次的计划是用河水来舒舒服服冲个澡。

    大神在河边建了一个水槽来洗澡,水槽排成整齐的格子,每相邻的两个之间都有水阀。要想让水进去,就必须打开这些水阀。这不是件容易的事情。因为有些圈里水阀关的很紧。因此打开水阀就很费劲。为了使花的力气最小,总是把水阀推向水阀质量差的一边。你的任务是计算最少得费多少劲。我们用水阀质量来描述这个值。

输入

第一行是长度w和宽度l,其中3 <= w,l <= 40。以下l行数据,描述了水阀质量,也就是我们所浪费体力的度量。数据的范围在1100之间。

输出

你得到的结果。所有的格子都必须进水,不然大神洗不干净。水是从左上角的格子进去的。

样例输入

4 3
3 5 2 1
7 3 4 8
1 6 5 7

样例输出

26


提示

来源

[提交][状态]