#2020. 奥特曼拯救zyx

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: new_user_4

题目描述

现实中奥特曼可能需要去保护地球,所以请不要帮人签到。

同时本故事纯属虚构,如有雷同,纯属巧合。

自学得到了老师的认可,但是帮他签到的却要受到正义的制裁!

现在在寝室里瑟瑟发抖,愤怒的现在就要将绳之以法来清除这个集训队的败类!

但不幸中的万幸是,拥有奥特曼的帮助!

奥特曼可以让学校的路面坍塌从而使得无法让人通过,但是路面有宽有窄,有坚硬的有松动的,所以切断每条边的代价不尽相同

作为光的驾驶者,你需要花费最少的能量来帮免于被抓的命运!

注意学校的地图是非常规则的,可以抽象成一张的网格图,并且在左上角,在右下角

一句话题意:网格图每条边都有权值,你需要花费最小的代价使得左上角的点和右下角的点不连通

图片Base64

输入格式

第一行包含两个整数 ,表示网格的大小。

表示网格的行数,表示网格的列数

接下来分为两部分:

  1. 第一部分共 行,每行 个数,表示切断横向道路的代价。
  2. 第二部分共 行,每行 个数,表示切断纵向道路的代价。

输出格式

输出一个整数,表示消耗能量的最小值

样例

输入#1

3 3
6 4
4 4
4 6
6 4 4
4 4 6

输出 #1

12

图片Base64

对于第一个测试样例,可以证明不存在比切断这两条红边的更优解存在。

输入#2

3 3
114514 4
4 4
4 114514
114514 4 4
4 4 114514

输出 #2

16

数据范围与提示

对于全部的测试点,保证 ,所有道路的权值均为不超过 的正整数。