题目描述

湖上有 $n$ 个岛屿排成一条线，编号 $1$ 到 $n$。相邻岛屿之间有桥，第 $j$ 座桥连接岛 $j$ 和 $j+1$。你目前在 $1$ 号岛，需要尽快到达 $n$ 号岛。

你有 $m$ 个休息等级可供选择（最多可休息 $m-1$ 次）。每多休息一次，过桥和休息的花费会变化：

• $A_{k,j}$（$k=1,\dots,m$）表示已经休息了 $k-1$ 次后，经过第 $j$ 座桥所需的时间。
• $B_{i,k}$（$k=1,\dots,m-1$）表示在岛 $i$ 进行第 $k$ 次休息所花费的时间，可能为负数。

你可以在任意岛屿上选择休息（消耗 $B_{i,k}$）或直接过桥。由于可以在相邻岛屿之间来回移动，请找到到达 $n$ 号岛的最短时间。你不必用完所有休息次数。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行 $n-1$ 个整数，第 $k$ 行表示 $A_{k,1},A_{k,2},\dots,A_{k,n-1}$。

接下来 $n$ 行，每行 $m-1$ 个整数，第 $i$ 行表示 $B_{i,1},B_{i,2},\dots,B_{i,m-1}$。若 $m=1$ 则该部分为空。

输出格式

一行一个整数，表示最短到达时间。

3 1
10 10

20

3 2
100 10
1 1
50
50
0

52

样例解释

样例 $1$：$m=1$，不能休息。直接 $1\xrightarrow{10}2\xrightarrow{10}3$，总时间 $20$。

样例 $2$：$m=2$，最多休息 $1$ 次。方案对比：

• 不休息：$1\xrightarrow{100}2\xrightarrow{10}3$，总 $110$
• 在岛 $1$ 休息（花费 $50$），休息后过桥（$A_{2,1}=1,A_{2,2}=1$）：$50+1+1=52$
• 在岛 $2$ 休息：$100+50+1=151$

最优为 $52$。

数据范围与约定

下发样例

下发样例下载