题目描述

小袁是一个天天吃人的学长，可怜的你需要逃离他的掌控，才能成功在这里呆下去。

武汉有着美丽的东湖，东湖非常非常的大，直径为 $2147483647$ 公里。湖上有 $n$ 个岛，其中每相邻两个岛之间有一座桥，有 $n-1$ 座桥，第 $i$ 座桥连接了编号为 $i$ 和 $i+1$ 的岛。

东湖中央是 $1$ 号岛，而在东湖上，唯一能够连接岸边的是 $n$ 号岛。每天有许许多多的市民在岛之间游玩。每一座桥有不同的长度，所以人们穿过岛屿需要一定的时间，然而这个时间和每个人的体力有关。现在你也要去岛上玩耍，不过你比较擅长调整和休息。休息会使你的体力恢复，所以每休息一次，你过同一座桥的时间就有可能越短。

有一天你正在湖心 $1$ 号岛上玩，但是突然听说小袁学长要空降到湖心 $1$ 号岛来欺负你。可是只有 $n$ 号岛才能通向湖岸。

不过你由于经常来东湖，所以可以根据经验估计出每一次休息后过每座桥的时间和在每座岛上休息所需要耗费的时间。（因为小袁讨厌懒惰的同学，所以你不能休息达到 $m$ 次，不然无论如何他都会欺负到你）。

你想估计你最快需要多久才能逃离小袁的掌控。当然，休息所需时间可能为负，表示你此次休息发生了时光倒流。

输入格式

第一行两个整数 $n$ 和 $m$ 表示有 $n$ 个岛，你最多休息 $m-1$ 次，也就是说你能预知休息 $m$ 次以前的所有岛的休息需要的时间和每座桥所用的时间。

接下来 $m$ 行，每行 $n - 1$ 个整数，分别表示在经过第 $0,1,2,\ldots,m-1$ 次休息后经过第 $1,2,\ldots,n-1$ 座桥的时间 $A_{i,j}$。

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

输出格式

一行一个整数表示：最短到达 $n$ 号岛的时间 $t$。

样例 #1

样例输入 #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

提示

数据范围

对前 $10\%$ 的数据 : $n \le 6$, $m \le 6$。

对前 $20\%$ 的数据 : $n \le 20$, $m \le 20$。

对前 $50\%$ 的数据: $n \le 300$, $m \le 300$。

对于全部数据 : $1\le n \le 1000$, $1\le m \le 1000$ , $0\le A_{i,j} \le 10^4$ , $|B_{i,j}| \le 10000$。