Perform巡回演出

题目描述:

　　Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出，本着普及古典音乐的目的，乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出，此后的几天里，音乐家们将每天搭乘一个航班从一个城市飞到另一个城市，最后才到达目的地Harp市(乐团可多次在同一城市演出)。
　　由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间，每一方向，航班表循环的周期都可能不同。现要求寻找一张花费费用最小的演出表。

输入格式:

　　包括若干个场景。每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始，音乐家们要在这n个城市作巡回演出,城市用1 ... n标号，其中1是起点Flute市，n是终点Harp市，接下来有n*(n-1)份航班表，一份航班表一行，描述每对城市之间的航线和价格，第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班，接下的n-1行是从城市2到其他城市(1，3，4 ... n ) 的航班，如此下去。
　　每份航班又一个整数d(1<=d<=30)开始，表示航班表循环的周期，接下来的d个非负整数表示1，2...d天对应的两个城市的航班的价格，价格为零表示那天两个城市之间没有航班。例如"3 75 0 80"表示第一天机票价格是75KOI，第二天没有航班，第三天的机票是80KOI，然后循环：第四天又是75KOI，第五天没有航班，如此循环。输入文件由n=k=0的场景结束。

输出格式:

　　对每个场景如果乐团可能从城市1出发，每天都要飞往另一个城市，最后(经过k天)抵达城市n，则输出这k个航班价格之和的最小值。如果不可能存在这样的巡回演出路线，输出0。

样例输入:

3 6 
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0

样例输出:

460
0

时间限制: 1000ms
空间限制: 128MB

---