You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

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

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

$kuro$自学得到了老师的认可，但是帮他签到的$zyx$却要受到正义的制裁！

现在$zyx$在寝室里瑟瑟发抖，愤怒的$37Lament$现在就要将$zyx$绳之以法来清除这个集训队的败类！

但不幸中的万幸是，$zyx$拥有奥特曼的帮助！

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

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

注意学校的地图是非常规则的，可以抽象成一张$N * M$的网格图，并且$37Lament$在左上角，$zyx$在右下角

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

Input Format

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

$N$表示网格的行数，$M$表示网格的列数$( 2 \leq N, M \leq 1000 )$

接下来分为两部分：

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

Output Format

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

Sample

输入#1

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

输出 #1

12

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

输入#2

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

输出 #2

16

Hint

对于全部的测试点，保证 $( 2 \leq N, M \leq 1000 )$，所有道路的权值均为不超过 $10^6$ 的正整数。