Magic Potion

Time limit2sMemory limit512 MB

Summary

Given a complete graph with edge weights and K potions that halve one trip's time, find the shortest time from city 0 to city 1.

Level: Medium5 of 10
Topics: Shortest path, Graph, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1
Input
```
3 1
094
904
440
```
Expected output
```
4.5
```
Example 2
Input
```
3 2
094
904
440
```
Expected output
```
4.0
```

Example 3

Input

Expected output

3.5