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