题目描述

神经网络可以看成一个 $n$ 行 $m$ 列的网格图，最左上角的坐标为 $(1, 1)$，最右下角的坐标为 $(n, m)$。网格中的边分为两类：

• 当 $1 \le x \le n$、$1 \le y < m$ 时，坐标 $(x, y)$ 和 $(x, y + 1)$ 之间有一条无向边，其边权为 $wa_{x,y}$（横向边）；
• 当 $1 \le x < n$、$1 \le y \le m$ 时，坐标 $(x, y)$ 和 $(x + 1, y)$ 之间有一条无向边，其边权为 $wb_{x,y}$（纵向边）。

神经网络具备传输信号的能力，信号需要从左上角的 $(1, 1)$ 通过网络中的边传递到右下角的 $(n, m)$。然而，某些边可能会突然失活，导致信号无法通过。当信号无法从 $(1, 1)$ 传递到 $(n, m)$ 时，整个神经网络将会失活。

小 C 定义了一个“稳定系数”，即使得整个神经网络失活（即断开起点 $(1, 1)$ 与终点 $(n, m)$ 的连通性）所需的最小边权和。

现在小 C 告诉你这个神经网络的各项边权，希望你求出它的稳定系数。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 分别表示网格的行数和列数。

接下来 $n$ 行，每行包含 $m-1$ 个整数，依次表示横向边的边权 $wa_{x,y}$。

接下来 $n-1$ 行，每行包含 $m$ 个整数，依次表示纵向边的边权 $wb_{x,y}$。

输出格式

输出一行，一个整数，表示该神经网络的稳定系数。

样例输入 1

2 2
4
2
3 0

样例输出 1

2

样例输入 2

3 3
2 0
1 6
4 1
5 1 1
4 2 5

样例输出 2

5

说明

样例解释

• 对于样例 $1$：对应网格图上的最小边权和割边方案，其权值和为 $2$。

• 对于样例 $2$：对应网格图上的最小边权和割边方案，其权值和为 $5$。

其它样例说明

• 样例 $3$：见选手目录下的 network/network3.in 和 network/network3.ans。该组数据满足 $n = 2$，$m \le 100$ 的条件。
• 样例 $4$：见选手目录下的 network/network4.in 和 network/network4.ans。该组数据满足 $n = 3$，$m \le 100$ 的条件。
• 样例 $5$：见选手目录下的 network/network5.in 和 network/network5.ans。该组数据满足 $n, m \le 100$ 的条件。

数据范围

对于所有测试数据，保证：

• $1 \le n, m \le 1000$
• $0 \le wa_{x,y}, wb_{x,y} \le 10^9$
• 保证所有的输入数值均为整数。

各测试点的限制如下表所示：

点击下载大样例