来源：张老师2026 CSP-J 4＋1拓展题第20套T4。

岛屿行程

题目描述

有排成一排的 $n$ 个岛，第 $i$ 座桥连接第 $i$ 个岛和第 $i+1$ 个岛。你在第 $1$ 个岛，想通过依次连接的桥抵达第 $n$ 个岛。每座桥的过桥时间不同，且会随你的体力状态升高而减少。在任意岛，你可以选择在当前岛休息（休息完可以继续休息），或是前往前一个岛或后一个岛（没错，由于各个岛的设施不同，恢复到不同体力所需的时间也是不同的，因此你可能会走回头路），休息可提高体力状态，至多休息 $m-1$ 次（也就是说你至多经历 $m$ 种体力状态，从初始状态编号为 $0$ 到最终状态编号为 $m-1$）。

你需要求出从第 $1$ 个岛出发到达第 $n$ 个岛所需的最短时间。

输入格式

第一行两个数字，$n$ 表示岛的数量，$m$ 表示最多可经历的状态数（最多休息 $m-1$ 次）。

接下来的 $m$ 行，每行 $n-1$ 个非负整数，表示在状态 $i$ 下通过第 $j$ 座桥的时间。

再接下来 $n$ 行，每行 $m-1$ 个整数，表示在第 $i$ 个岛进行第 $j$ 次休息所需的时间（可能为负）。

输出格式

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

样例输入

5 5
50 50 100 100
50 50 100 100
40 40 80 80
30 30 60 60
20 20 40 40
60 60 60 60
40 40 30 30
30 20 20 20
20 20 20 20
0 0 0 -1000

样例输出

-710

数据范围

对于 $10\%$ 的数据，$n,m\le 6$。

对于 $20\%$ 的数据，$n,m\le 20$。

对于 $50\%$ 的数据，$n,m\le 300$。

对于 $100\%$ 的数据，$1\le n,m\le 1000$，$0\le A_{i,j},|B_{i,j}|\le 10^4$。

本题共 10 组测试，每组 10 分。同组测试全部通过才能获得该组分数，各组分数累加。