你是某在线地图服务中“路线追踪”功能的忠实粉丝。你喜欢在地图上绘制图案：首先设计一个看起来像目标图像的路线，然后用移动设备实际追踪该路线。

有一天，你注意到这个城镇有一个网格状的铁路网络。在地图上，有 $H \times W$ 个车站，它们位于由 $H$ 条水平线和 $W$ 条垂直线组成的网格上。每个交叉点恰好有一个车站，且每个车站都与它垂直或水平相邻（不包括对角线）的所有车站相连。连接可能具有不同的费用，但从车站 $A$ 移动到车站 $B$ 的费用始终与从 $B$ 移动到 $A$ 的费用相同。如果你多次使用同一条连接，则每次使用时都必须支付相应的费用。

你计划通过至少经过铁路网络上的所有连接一次来在地图上绘制一个完整的网格。你必须在同一个车站开始并结束路线。在这些约束条件下，你希望最小化总旅行成本。由于你也很擅长编程，你决定编写一个程序来计算设计最优路线时的最小成本。

输入格式

第一行包含两个整数 $H$ ($2 \le H \le 100$) 和 $W$ ($2 \le W \le 100$)，表示铁路网络网格由 $H$ 行和 $W$ 列组成。设 $(i, j)$ 为从上往下第 $i$ 行、从左往右第 $j$ 列的交叉点。

接下来的 $H-1$ 行，第 $i$ 行包含 $W$ 个整数，其中第 $j$ 个整数表示在车站 $(i, j)$ 和车站 $(i+1, j)$ 之间移动的费用。

接下来的 $H$ 行，第 $i$ 行包含 $W-1$ 个整数，其中第 $j$ 个整数表示在车站 $(i, j)$ 和车站 $(i, j+1)$ 之间移动的费用。

所有费用均在 $0$ 到 $10^9$ 之间。

输出格式

输出一行，包含一个整数：通过乘坐铁路网络上的火车绘制完整网格所需的最小成本。

样例

样例输入 1

2 4
2 2 2 2
1 1 1
1 1 1

样例输出 1

16

样例输入 2

4 3
3 2 0
6 1 0
7 1 6
7 5
8 1
8 3
3 5

样例输出 2

76