机器人装配

题目描述

完成了Nintendo Switch的订单，F工厂又接到了一笔装配机器人的订单。F工厂决定投入n条生产线装配机器人。

已知：

1. 这n条生产线各有m个装配站，对于每条生产线的第i个装配站需要完成的工序都是相同的，只是完成的时间有所不同；
2. 机器人需要按顺序从第一个装配站开始装配，然后进入第二个、第三个……最后进入第m个装配站装配完成，但装配机器人完成各道工序可以在不同的流水线进行；
3. 生产前进入流水线的第一个装配站、在最后一个装配站装配完成出流水线的时间均忽略不计；
4. 当东西在第i个装配站完成工序时，可以将东西切换到任意一条流水线的第i+1个装配站继续装配，当且仅当发生流水线转换时有额外的时间花费且花费时间可能不相同。

F工厂老板想知道的是：完成装配一台机器人最少需要多少时间？

输入

多组输入数据（不超过5组）。

每组数据第一行为2个整数，为流水线条数n和装配站个数m。其中$1 \leq n \leq 10$，$1 \leq m \leq 1000$

接下来对于$m$个装配站的数据如下：

1. 对于第$j$个装配站完成的工序，第一行为$n$个正整数，表示完成该工序在第$i$条流水线需要完成的时间$t$，保证$1 \leq t \leq 100$；
2. 当$1 \leq j \leq m-1$时，接下来$n$行，每行$n$个非负整数，为n*n的矩阵A，A[x][y]代表东西在第$x$条流水线的第$j$个装配站装配完成后，切换到第$y$条流水线的第$j+1$个装配站需要花费的时间。保证当$x=y$时，$A[x][y]=0$，其余情况$1 \leq A[x][y] \leq 100$
3. 当$j=m$时，无流水线切换数据。

具体参见样例及解释。

输出

对于每组数据，输出一行，F工厂完成装配一台机器人需要的时间最小值。

样例

Input

1 3
5
0
6
0
7
2 3
5 4
0 1
1 0
6 8
0 1
2 0
7 2

Output

18
14

样例解释

对于第一组数据，只有1条流水线、3个装配站，无切换流水线的情况，A[1][1]=0，构成的流水线为5-->6-->7，最小时间为18

对于第二组数据，有2条流水线、3个装配站。其中，对于第一个装配站所要完成的第一道工序，第一条流水线需要花费时间为5，第二条流水线需要时间为4，完成第一道工序后切换流水线的矩阵A1为:

0 1
1 0

对于第二个装配站所要完成的第二道工序，第一条流水线需要花费时间为6，第二条流水线需要时间为8，完成第二道工序后切换流水线的矩阵A2为：

0 1
2 0

对于第三个装配站所要完成的第三道工序，第一条流水线需要花费时间为7，第二条流水线需要时间为2，完成后出流水线时间忽略不计。

所构成的生产线组如下图所示（没有标数字表示该传输过程花费的时间为0）：

我们可以通过红线（即4-->6-->2的线路）得到最少的装配时间：4+1+6+1+2=14；也可以通过蓝线（即4-->8-->2的线路）得到同样最少的装配时间：4+0+8+0+2=14。本题只需要求出最少的装配时间即可，因此输出为14.