CF62E.World Evil

As a result of Pinky and Brain's mysterious experiments in the Large Hadron Collider some portals or black holes opened to the parallel dimension. And the World Evil has crept to the veil between their world and ours. Brain quickly evaluated the situation and he understood that the more evil tentacles creep out and become free, the higher is the possibility that Brain will rule the world.

The collider's constriction is a rectangular grid rolled into a cylinder and consisting of n rows and m columns such as is shown in the picture below:

In this example n = 4, m = 5. Dotted lines are corridores that close each column to a ring, i. e. connect the n-th and the 1-th rows of the grid.

In the leftmost column of the grid the portals are situated and the tentacles of the World Evil are ready to creep out from there. In the rightmost column the exit doors are located. The tentacles can only get out through those doors. The segments joining the nodes of the grid are corridors.

Brain would be glad to let all the tentacles out but he faces a problem: the infinite number of tentacles can creep out of the portals, every tentacle possesses infinite length and some width and the volume of the corridors are, unfortunately, quite limited. Brain could approximately evaluate the maximal number of tentacles that will be able to crawl through every corridor.

Now help the mice to determine the maximal number of tentacles of the World Evil that will crawl out of the Large Hadron Collider.

由于Pinky和Brain在大型强子对撞机（LHC）中进行的神秘实验，一些传送门或黑洞打开了通往平行维度的通道，世界之恶已悄然渗透至他们所在世界与我们世界之间的帷幕之中。Brain迅速评估了当前局势，并意识到：从传送门中钻出并获得自由的邪恶触手越多，Brain统治世界的可能性就越高。

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

本例中 $n = 4$，$m = 5$。图中虚线表示各列内部的通道，将每列首尾相连形成环状结构，即连接网格的第 $n$ 行与第 $1$ 行。

网格最左侧一列布置有传送门，世界之恶的触手正准备从此处钻出；最右侧一列则设有出口门，触手只能经由这些门逃逸出去。连接网格节点的线段代表通道。

Brain本乐于放行所有触手，但他面临一个问题：传送门中可涌出无穷多条触手，每条触手具有无限长度及一定宽度，而通道的容积却十分有限。Brain已能大致估算出每条通道所能通过的触手的最大数量。

现在，请协助这两只老鼠，计算出能够从大型强子对撞机中成功逃逸的世界之恶触手的最大数量。

The first line of the input file contains two integers n and m (2 ≤ n ≤ 5, 2 ≤ m ≤ 105). They are the sizes of the Large Hadron Collider grid. The next m - 1 lines contain n numbers each. They are the horizontal corridors' capacities. The next m lines contain n numbers each. They are the vertical corridors' capacities. Corridors are described from left to right and from top to bottom. Every n-th vertical corridor connects nodes of the n-th and 1-th rows. A corridor's capacity is a non-negative integer that does not exceed 109.

输入文件的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 5$，$2 \leq m \leq 10^5$），表示大型强子对撞机（LHC）网格的尺寸。接下来的 $m-1$ 行，每行包含 $n$ 个数字，表示水平通道的容量。再接下来的 $m$ 行，每行也包含 $n$ 个数字，表示垂直通道的容量。通道按从左到右、从上到下的顺序描述。每个第 $n$ 条垂直通道连接第 $n$ 行与第 $1$ 行的节点。通道的容量为非负整数，且不超过 $10^9$。

Print a single number, the number of the World Evil tentacles Pinky and Brain will command.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

输出一个整数，表示粉红豹（Pinky）和大脑（Brain）将指挥的世界邪恶触手的数量。

请注意，在 C++ 中请勿使用 %lld 格式说明符来读取或写入 64 位整数。推荐使用 cout（当然也可以使用 %I64d）。