问题 25480 --mine

25480: mine

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

题目描述

GJQHY同学经常打游戏,因此总是被给类奇葩的游戏吓到……

即时策略游戏中,资源是必不可少的。但由于这个奇葩的游戏有着奇葩的规则,所以二人总是很难采到最多的矿。

矿区是被划分成一个n*m的矩形区域。每一小块区域里有NEW矿和BE矿两种矿,而且蕴藏量是已知的, 并且GJQ.HY在矿区的北边和西边分别设置了NEW矿和BE矿的收集站。你的任务是设计一个管道运输系统,使得运送的NEW矿和BE矿的总量最多。

管道的型号有两种,一种是东西向,一种是南北向。在一个格子内你能建造一种管道,但不能两种都建。如果两个同类型管道首位相接,它们就可以被连接起来。

另外这些矿物都十分不稳定,因此它们在运送过程中都不能拐弯。这就意味着如果某个格子上建有南北向管道,但是它北边的格子建有东西向管道,那么这根南北向管道内运送的任何东西都将丢失。迚一步地,运到NEW矿收集站的BE矿也会丢失,运到BE矿收集站的NEW矿也会丢失。

输入

第一行包含两个整数nm,表示矿区大小。

以下n行,每行m个整数,其中第i行第j个整数G[ i , j ] 描述各个格子上的BE矿数量。接下来以类似的矩阵表示各个格子上的NEW矿数量。


对于30%的数据: 0<= nm <=100;

对于100%的数据: 0<= n, m <=1000;

0<= G[ i, j ] <=1000.

输出

仅一个整数, 表示最多可以采集到的NEW矿和BE矿的总量。

样例输入

4 4 
0 0 10 9 
1 3 10 0 
4 2 1 3 
1 1 20 0 
10 0 0 0 
1 1 1 30 
0 0 5 5 
5 10 10 10

样例输出

98

提示

来源

[提交][状态]