A22564.狗哥采矿

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

又是一节平静的语文课。

狗哥闲来无事,出来了这么一道题。
一个 n×mn\times m 的矩阵中,每个格子内有两种矿 yeyenum 和 bloggium,并且知道它们在每个格子内的数量是多少。最北边有 bloggium 的收集站,最西边有 yeyenum 的收集站。现在要你在这些格子上面安装向北或者向西的传送带(每个格子只能装一种)。问最多能采到多少矿?

输入格式

第一行包含两个整数 n,m, (1n500,1m500)n,m,\ ( 1 ≤ n ≤ 500, 1 ≤ m ≤ 500)。接下来 nnmm 列,表示每个格子中可以传送到 yeyenum 的数量(小于 10001000),再接下来 nnmm 列,表示每个格子中可以传送到 bloggium 的数量。n,mn, m 同时为 00 时结束。

输出格式

每组测试数据仅输出一个数,表示最多能采到的矿。

输入输出样例

  • 输入#1

    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 
    0 0

    输出#1

    98

说明/提示

传输过程中不能转弯,只能走直路。

首页