该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

逃离湖心

题目描述

Y 同学位于一片湖泊中央，需要尽快逃到岸边。

湖中共有 $n$ 个岛屿，按照从湖心到岸边的顺序编号为 $1\sim n$。对于每个 $1\le i<n$，第 $i$ 个岛与第 $i+1$ 个岛之间有一座桥,每座桥均可以双向通行，

Y 同学初始位于第 $1$ 个岛，只有到达第 $n$ 个岛后才能离开湖泊。

Y 同学可以在岛上休息。休息会改变他之后通过桥梁所需的时间，但整个过程中最多只能休息 $m-1$ 次。

若 Y 同学当前已经休息了 $j$ 次，其中 $0\le j<m$，则通过第 $i$ 座桥，也就是从第 $i$ 个岛移动到第 $i+1$ 个岛 或者 从第 $i + 1$ 个岛移动到第 $i$ 个岛，需要花费 $A_{j,i}$ 的时间。

若 Y 同学准备在第 $i$ 个岛进行第 $j$ 次休息，其中 $1\le j<m$，则此次休息需要花费 $B_{i,j}$ 的时间。

休息所需时间可能为负数，表示此次休息会使当前时刻向前倒退。

Y 同学可以在同一个岛上连续休息多次，也可以不在某些岛上休息。在完成第 $m-1$ 次休息后，不能再进行休息。

请你求出 Y 同学从第 $1$ 个岛出发，到达第 $n$ 个岛所需的最短时间。

输入格式

第一行包含两个整数 $n,m$，分别表示岛屿数量和休息次数状态的数量。Y 同学最多可以休息 $m-1$ 次。

接下来 $m$ 行，每行包含 $n-1$ 个整数。

第 $j+1$ 行的第 $i$ 个整数为 $A_{j,i}$，表示已经休息 $j$ 次后，通过第 $i$ 座桥所需的时间，其中 $0\le j<m$，$1\le i<n$。

接下来 $n$ 行，每行包含 $m-1$ 个整数。

其中第 $i$ 行的第 $j$ 个整数为 $B_{i,j}$，表示在第 $i$ 个岛进行第 $j$ 次休息所需的时间，其中 $1\le i\le n$，$1\le j<m$。

输出格式

输出一行一个整数，表示 Y 同学从第 $1$ 个岛到达第 $n$ 个岛所需的最短时间。

样例

样例输入 #1

5 5
100 10 100 100
100 10 100 1000
100 5 100 100
50 5 50 50
50 5 5 50
50 50 50 50
50 10 10 50
10 5 100 10
50 50 100 50
50 50 100 50

样例输出 #1

210

数据范围与约定

对于 $100\%$ 的数据，保证：$1\le n,m\le1000$,$0\le A_{j,i}\le10^4$,$\lvert B_{i,j}\rvert\le10^4$；

• 答案在有符号 $64$ 位整数的表示范围内。

• 特殊性质 A：保证所有休息时间均为 $0$。
• 特殊性质 B：保证对所有合法的 $i,j$，均有 $A_{j,i}=A_{0,i}$。
• 特殊性质 C：保证所有 $B_{i,j}\ge0$。