A2853. 狗哥采矿
编程题
普及+/提高
知识点
题目描述
又是一节平静的语文课。
狗哥闲来无事，出来了这么一道题。
一个 $n\times m$ 的矩阵中，每个格子内有两种矿 yeyenum 和 bloggium，并且知道它们在每个格子内的数量是多少。最北边有 bloggium 的收集站，最西边有 yeyenum 的收集站。现在要你在这些格子上面安装向北或者向西的传送带（每个格子只能装一种）。问最多能采到多少矿？
狗哥闲来无事，出来了这么一道题。
一个 $n\times m$ 的矩阵中，每个格子内有两种矿 yeyenum 和 bloggium，并且知道它们在每个格子内的数量是多少。最北边有 bloggium 的收集站，最西边有 yeyenum 的收集站。现在要你在这些格子上面安装向北或者向西的传送带（每个格子只能装一种）。问最多能采到多少矿？
输入格式
第一行包含两个整数 $n,m,\ ( 1 ≤ n ≤ 500, 1 ≤ m ≤ 500)$。接下来 $n$ 行 $m$ 列，表示每个格子中可以传送到 yeyenum 的数量（小于 $1000$），再接下来 $n$ 行 $m$ 列，表示每个格子中可以传送到 bloggium 的数量。$n, m$ 同时为 $0$ 时结束。
输出格式
每组测试数据仅输出一个数，表示最多能采到的矿。
输入输出样例
输入 #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
说明/提示
传输过程中不能转弯，只能走直路。