巡回演出问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Flute市的Phlharmoniker乐团是一支非常优秀的管弦乐团,一直以来在国际古典乐坛上有着很高的地位。2000年的乐季又开始了,乐团在音乐总监C.M.R.和乐团指挥L.Y.M.的带领下到Harp市作一次大型演出。本着普及古典音乐的目的,L.Y.M决定在到达Harp市之前先在周围一些小城市做一段时间的巡回演出。此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市。请注意,由于乐团的演奏风格多样,适演曲目极多,所以乐团可以多次来到同一个城市进行演出。

虽然演出的酬劳相当可观,但还是要精打细算,尽量减少路费。可这并不容易,由于航线的费用和班次每天都在变。城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同。

经过整整一晚的思考,我们的音乐家终于想出了预定机票的最佳方案。你知道他们是怎么样做的吗?

Input

输入数据包含若干个场景。每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始。音乐家们要在这n个城市里作巡回演出。城市用1,2,...,n编号,其中1是起点Flute市,n是终点Harp市,k是经过的天数。接下来将有n(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格。第1组n-1份航班表对应从城市1到其他所有城市(2,3,...,n)的航班,接下来的n-1行是从城市2到其他城市(1,3,4,...,n)的航班,如此下去。

每份航班表由一个整数d(1<=d<=30)开始,表示航班表循环的周期。接下来的d个非负整数,表示1,2,...,d天对应的两个城市的航班的价格。价格为0表示那天两个城市之间没有航班。例如,航班表“3 75 0 80”表示第1天的机票是75 KOI(KOI是信息学竞赛专用货币单位),第2天没有航班,第3天的机票是80 KOI,然后循环:第4天又是75 KOI,第5天没有航班,如此循环。

输入数据由n=k=0的场景结束。

Output

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

Sample Input

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

Sample Output

460
0

Hint

Source