6955: mine
内存限制：128 MB
时间限制：1 S
题面：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
GJQ和HY同学经常打游戏，因此总是被给类奇葩的游戏吓到……
即时策略游戏中，资源是必不可少的。但由于这个奇葩的游戏有着奇葩的规则，所以二人总是很难采到最多的矿。
矿区是被划分成一个n*m的矩形区域。每一小块区域里有NEW矿和BE矿两种矿，而且蕴藏量是已知的， 并且GJQ.HY在矿区的北边和西边分别设置了NEW矿和BE矿的收集站。你的任务是设计一个管道运输系统，使得运送的NEW矿和BE矿的总量最多。
管道的型号有两种，一种是东西向，一种是南北向。在一个格子内你能建造一种管道，但不能两种都建。如果两个同类型管道首位相接，它们就可以被连接起来。
另外这些矿物都十分不稳定，因此它们在运送过程中都不能拐弯。这就意味着如果某个格子上建有南北向管道，但是它北边的格子建有东西向管道，那么这根南北向管道内运送的任何东西都将丢失。迚一步地，运到NEW矿收集站的BE矿也会丢失，运到BE矿收集站的NEW矿也会丢失。输入格式
第一行包含两个整数n和m，表示矿区大小。
以下n行，每行m个整数，其中第i行第j个整数G[ i , j ] 描述各个格子上的BE矿数量。接下来以类似的矩阵表示各个格子上的NEW矿数量。
对于30%的数据： 0<= n，m <=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