世界邪恶

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

由于 Pinky 和 Brain 在大型强子对撞机中进行了一些神秘实验，一些通往平行维度的传送门或黑洞被打开了。世界邪恶已经渗透到了他们的世界与我们的世界之间的薄膜上。Brain 很快评估了形势，他明白，越多的邪恶触手爬出来变得自由，Brain 统治世界的可能性就越大。

对撞机的结构是一个被卷成圆柱体的矩形网格，由 $n$ 行 $m$ 列组成，示意图如下：

在这个例子中 $n=4$，$m=5$。虚线表示使每一列首尾相连的通道，即连接第 $n$ 行与第 $1$ 行。

在网格最左侧的一列分布着传送门，而世界邪恶的触手正准备从这里爬出来。在网格最右侧的一列有出口门，触手只能通过这些门爬出去。连接网格节点的线段是走廊。

Brain 很乐意让所有触手都爬出来，但遇到了一个问题：传送门可以释放无限数量的触手，每一条触手都拥有无限长度和一定宽度，然而这些走廊的容量却很有限。Brain 仅能约略评估每条走廊能够通过的触手的最大数量。

现在，请帮助老鼠们计算能够从大型强子对撞机中爬出的世界邪恶触手的最大数量。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 5$，$2 \leq m \leq 10^{5}$），表示大型强子对撞机网格的尺寸。

接下来的 $m-1$ 行，每行包含 $n$ 个整数，表示每条水平走廊的容量。

再接下来的 $m$ 行，每行包含 $n$ 个整数，表示每条垂直走廊的容量。走廊的描述从左到右，从上到下。每个第 $n$ 个垂直走廊连接网格的第 $n$ 行与第 $1$ 行。

每条走廊的容量是一个不超过 $10^9$ 的非负整数。

输出格式

输出一行，表示 Pinky 和 Brain 能够指挥的世界邪恶触手的最大条数。

请不要在 C++ 中使用 %lld 格式符进行 64 位整数的输入输出。建议使用 cout（或 %I64d）。

样例输入 1

3 4
4 4 4
1 1 5
5 5 3
4 1 2
1 3 1
3 5 4
1 4 3

样例输出 1

7

样例输入 2

2 2
9 2
2 3
6 1

样例输出 2

11

数据范围

对所有数据：$2\le n\le5$，$2\le m\le10^5$，每条走廊的容量在 $[0,10^9]$ 内。

各子任务数据彼此独立计分。