题目翻译

题目名称：逃脱计划

描述
刺耳的刹车声、探照灯的光束、此起彼伏的警笛声，警车从四面八方围堵而来——神偷特里莎·快指又一次得手了！虽然偷走《蒙娜丽莎》比预想的更困难，但作为世界顶尖的艺术品大盗，她早已习惯了应对突发状况。此刻，她腋下夹着装裱好的画框，正拼命奔向前往戴高乐机场的北线地铁。

但比偷画更重要的是甩掉即将追捕她的警察。特里莎的计划很简单：她将在几天内辗转多个城市，每天搭乘一班飞机。当她确信警方已经失去她的踪迹时，就会飞往亚特兰大，与她的“客户”（仅以“P先生”代称）接头并交付画作。

然而，即便是在偷窃天价艺术品的行当里，如今也不得不精打细算。特里莎希望尽可能节省逃亡途中的机票开支。但这并不容易，因为航空公司的票价和航班可用性每天都会变化。每条航线的价格和可飞行日期取决于起飞城市、到达城市以及飞行日期。每对城市之间的航班有一个“周期表”，每隔几天循环一次，且不同航线、不同方向的周期可能各不相同。

尽管特里莎擅长偷画，但在预订航班时却容易犯晕。这时就需要你的帮助了。

输入格式
输入包含多个特里莎的逃脱场景描述。每个场景的第一行是两个整数 n 和 k，其中 n 是可能途经的城市数量，k 是她需要搭乘的航班数。城市编号为 1 到 n，其中 1 是巴黎（起点），n 是亚特兰大（终点）。数据满足 2 ≤ n ≤ 10，1 ≤ k ≤ 1000。

接下来的 n(n−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，第 2 天无航班，第 3 天票价 80，之后循环（第 4 天 75，第 5 天无航班，依此类推）。

输入以 n = k = 0 结束。

输出格式
对每个场景，首先输出场景编号（如样例所示）。如果特里莎能在 k 天内从城市 1 出发，每天飞往不同城市（且不连续两天停留同一城市），最终抵达城市 n，则输出 The best flight costs x.（x 为最小总花费）。否则输出 No flight possible.。

每个场景输出后空一行。

样例输入 1

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

样例输出 1

Scenario #1
The best flight costs 460.

Scenario #2
No flight possible.

来源
1997 年西南欧地区竞赛