Always on the run

Screeching tires. Searching lights. Wailing sirens. Police cars everywhere. Trisha Quickfinger did it again! Stealing the 'Mona Lisa' had been more difficult than planned, but being the world's best art thief means expecting the unexpected. So here she is, the wrapped frame tucked firmly under her arm, running to catch the northbound metro to the airport.

But even more important than actually stealing the painting is shaking off the police who will soon be following her. Trisha's plan is simple: for several days she will fly from one city to another, taking exactly one flight per day. When she is reasonably sure the police have lost her trail, she will fly to Atlanta and meet her 'customer' (known only as Mr. P.) to deliver the painting.

Her plan is complicated by the fact that nowadays, even when you are stealing expensive art, you have to watch your spending budget. Trisha therefore wants to spend as little money as possible on her escape flights. This is not easy, since airline prices and flight availability vary from day to day. The price and availability of a connection depend on the two cities involved and on the day of travel. Every ordered pair of cities has a flight schedule that repeats every few days; the length of the period may differ for each pair of cities and for each direction.

Although Trisha is good at stealing paintings, she easily gets confused when booking flights. This is where you come in.

The input contains the descriptions of several scenarios.

Every scenario starts with a line containing two integers $n$ and $k$. Here $n$ is the number of cities through which Trisha's escape may take her, and $k$ is the number of flights she will take. The cities are numbered $1, 2, \ldots, n$, where city $1$ is her starting point and city $n$ is her final destination. The values satisfy $2 \le n \le 10$ and $1 \le k \le 1000$.

Next come $n(n-1)$ flight schedules, one per line, describing the connection for every ordered pair of distinct cities. The first $n-1$ schedules are the flights from city $1$ to all other cities ($2, 3, \ldots, n$), the next $n-1$ lines are the flights from city $2$ to all others ($1, 3, 4, \ldots, n$), and so on.

Each flight schedule starts with an integer $d$, the length of its period in days, with $1 \le d \le 30$. It is followed by $d$ non-negative integers giving the cost of the flight on days $1, 2, \ldots, d$. A cost of $0$ means there is no flight on that day.

For example, the schedule 3 75 0 80 means the flight costs $75$ on day $1$, is unavailable on day $2$, costs $80$ on day $3$, and then the cycle repeats: it costs $75$ on day $4$, is unavailable on day $5$, and so on.

The input ends with a scenario in which $n = k = 0$; this scenario must not be processed.

For each scenario, first print its number in the form Scenario #i, where $i$ counts the scenarios starting from $1$.

Trisha starts in city $1$. On each of the $k$ days she flies to a city different from the one she is currently in. If it is possible for her to arrive in city $n$ after exactly $k$ flights, print The best flight costs x., where $x$ is the least total cost of the $k$ flights. Otherwise, print No flight possible.

Separate consecutive scenarios with a single blank line.