Magic Potion

There are $N$ cities numbered 0 to $N-1$. Every pair of cities is directly connected, so travel between any two cities is always possible.

You are given the travel time between every pair of cities and the number of magic potions $K$ that you hold. Drinking a magic potion lets you move twice as fast as usual. When you travel from one city to another you may use one magic potion, and that trip then takes half its usual time. You cannot spend two or more potions on a single trip, and you do not have to drink every potion you hold.

Find the shortest time to get from city 0 to city 1.

The first line contains the number of cities $N$ and the number of magic potions $K$. ($2 \le N \le 50$, $0 \le K \le 50$)

The next $N$ lines contain the travel time matrix. Each line is $N$ digits written with no separators. The value in row $i$, column $j$ is the time to travel from city $i$ to city $j$, and rows and columns are both counted from 0. Each time is an integer between 0 and 9.

For all $i$ and $j$, the value in row $i$, column $j$ equals the value in row $j$, column $i$, and the value in row $i$, column $i$ is always 0.

Print the shortest time from city 0 to city 1 with exactly one digit after the decimal point. The answer is always a multiple of 0.5, so one decimal digit represents it exactly.