매직 포션

0번부터 $N-1$번까지 번호가 붙은 도시 $N$개가 있다. 도시는 모두 서로 직접 연결되어 있어서 임의의 두 도시 사이를 이동하는 것이 항상 가능하다.

모든 도시 사이를 이동하는 데 걸리는 시간과 가지고 있는 매직 포션의 개수 $K$가 주어진다. 매직 포션을 마시면 평소보다 두 배 빠르게 움직일 수 있다. 한 도시에서 다른 도시로 이동할 때 매직 포션을 하나 사용할 수 있고, 그 이동에 걸리는 시간은 절반이 된다. 한 번의 이동에 포션을 두 개 이상 쓸 수는 없다. 가진 포션을 모두 마실 필요는 없다.

도시 0에서 도시 1까지 가는 가장 빠른 시간을 구하라.

첫째 줄에 도시의 개수 $N$과 매직 포션의 개수 $K$가 주어진다. ($2 \le N \le 50$, $0 \le K \le 50$)

둘째 줄부터 $N$개의 줄에 이동 시간 행렬이 주어진다. 각 줄은 구분자 없이 붙어 있는 숫자 $N$개다. 행렬의 $i$행 $j$열 값은 도시 $i$에서 도시 $j$로 이동하는 데 걸리는 시간이고, 행과 열은 모두 0번부터 센다. 시간은 0 이상 9 이하의 정수다.

모든 $i$, $j$에 대해 $i$행 $j$열 값과 $j$행 $i$열 값은 같고, $i$행 $i$열 값은 항상 0이다.

도시 0에서 도시 1까지 가는 가장 빠른 시간을 소수점 아래 한 자리까지 출력한다. 답은 항상 0.5의 배수여서 소수점 아래 한 자리로 정확히 나타낼 수 있다.