125. 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