UVA590 Always on the run

## 问题描述 刺耳的轮胎声、搜索灯、疯狂作响的警报器、遍地的警车，特丽莎•金手指又来偷“蒙娜丽莎”了！这次比以前更困难，可她是世界上最好的小偷！所以她偷出了画，将画框裹着牢牢地夹在她的胳膊下，跑步到戴高乐机场。 但比偷画更重要的是摆脱警察的追捕。特丽莎的计划很简单：她将花几天时间坐飞机从一个城市到另一个城市，每天乘坐一个航班。当她相当肯定警方已经失去了她的线索时，她将飞往亚特兰大，并与她的客户（只知道为某正六面体）见面。 她的计划是复杂的，事实上，现在，即使你偷了昂贵的画，可以用来卖很多钱，你也必须做一下开支预算。特丽莎想在她逃跑的航班上花最少的钱。这是不容易的，因为每天航空公司航班的价格不同。一个航班的价格取决于涉及的两个城市和日期。每两个城市都有一个“航班时刻表”，每隔几天重复一次。每个城市的到其他不同城市的航班价格的周期长度可能是不同的。 虽然特丽莎善于偷画，但她不知道如何花最少的钱乘坐航班以满足她的要求。请你帮她计算。

输入包含若干情景特丽莎试图逃跑的描述。每一个描述首先行包含两个整数 $n$ 和 $k$，$n$ 是特丽莎逃脱过程中可能需要经过的城市数量，$k$ 是航班数量。城市的编号为 $1,2,\cdots,n$，其中 $1$ 是巴黎，她的出发点，$n$ 是亚特兰大，她最终的目的地。 接下来的 $n (n - 1)$ 行，给出 $n (n - 1)$ 个航班时刻表，每行一个，描述了每一个可能的城市之间的航班线路。前 $(n - 1)$ 个航班时间表对应的航班是从城市 $1$ 到所有其他城市 $(2,3,\cdots，n)$ 的航班，下 $(n - 1)$ 行的那些时刻表描述了从城市2到所有其他城市 $(1,3,4,\cdots,n)$，等等。 关于时刻表的描述，首先有一个整数 $d$，航班价格重复周期的长度，$d$ 是小于 $1000$ 的非负整数；后面的 $d$ 个数代表这两个城市之间每天的飞行成本（从第 $1$ 天到第 $d$ 天，然后循环）。成本为 $0$ 代表这天这两个城市之间没有航班。 例如，`3 75 0 80` 表示：第一天的价格是 $75$，第二天没有航班，第三天价格是 $80$，然后周期重复：第四天的价格是 $75$，第五天没有航班…… $n = k = 0$ 代表输入结束。

对于输入中的每一个场景，首先输出这是第几个场景，如样例输出中所示。如果特丽莎可能以这种方式“旅行” $k$ 天，即第 $1$ 天从第 $1$ 个城市开始，每天飞到和前一天不同的城市，最后（在第 $k+1$ 日）抵达城市 $n$。 请输出最少的成本 $x$（其中 $x$ 是 $k$ 次航班的最少费用），如果特丽莎不可能以这样的方式“旅行”，输出 `No flight possible.`。 注意在每一个场景后打印一个空白行。