由于 Pinky 和 Brain 在大型强子对撞机中进行的神秘实验,一些门户或黑洞打开了平行维度。世界上的邪恶已经爬进了他们的世界和我们的世界之间的面纱。布莱恩很快评估了局势,他明白,越多邪恶的触手爬出并获得自由,布莱恩统治世界的可能性就越大。
碰撞体的收缩部分是一个卷成圆柱体的矩形网格,由 n 行和 m 列组成,如下图所示:
在此示例中,n = 4,m = 5。虚线是将每列封闭为环的走廊,即。 e.连接网格的第 n 行和第 1 行。
网格的最左边一列有传送门,世界邪恶的触手已准备好从那里爬出来。出口门位于最右边的一列中。触手只能从那些门出去。连接网格节点的部分是走廊。
Brain很乐意放出所有的触手,但他面临一个问题:无数的触手可以从传送门中爬出,每根触手都拥有无限的长度和一定的宽度,不幸的是,走廊的体积非常有限。大脑可以大致评估能够爬过每个走廊的触手的最大数量。
现在帮助老鼠确定将从大型强子对撞机中爬出的世界邪恶触手的最大数量。
输入
输入文件的第一行包含两个整数 n 和 m (2 ≤ n ≤ 5, 2 ≤ m ≤ 105)。它们是大型强子对撞机网格的大小。接下来的 m - 1 行每行包含 n 个数字。它们是水平走廊的容量。接下来的 m 行每行包含 n 个数字。它们是垂直走廊的容量。走廊是从左到右、从上到下描述的。每第n条垂直走廊连接第n行和第1行的节点。走廊的容量是一个不超过 109 的非负整数。
输出
打印一个数字,世界邪恶触手 Pinky 和 Brain 将指挥的数字。
请不要使用 %lld 说明符在 C++ 中读取或写入 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