12913번 - 매직 포션 스페셜 저지

0부터 N-1까지 번호가 매겨져있는 N개의 도시가 있다. 도시는 모두 연결되어 있기 때문에, 임의의 두 도시를 여행하는 것은 항상 가능하다.

모든 도시 사이를 이동하는데 걸리는 시간과 가지고 있는 매직 포션의 개수 K가 주어진다. 매직 포션은 평소보다 두 배 빠르게 움직일 수 있게 해준다. 한 도시에서 다른 도시로 이동할 때, 매직 포션을 하나 사용할 수 있다. 

도시 0에서 도시 1을 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 모든 매직 포션을 다 마실 필요는 없다.

첫째 줄에 도시의 개수 N과 가지고 있는 매직 포션의 개수 K가 주어진다. (2 ≤ N ≤ 50, 0 ≤ K ≤ 50)

둘째 줄부터 N개의 줄에는 도시사이의 거리가 주어진다. i번 줄의 j번째 수는 i번 도시에서 j번 도시를 가는데 걸리는 시간이다. 시간은 0보다 크거나 같고, 9보다 작거나 같은 자연수이다.

i번째 줄의 j번째 수는 j번째 줄의 i번째 수와 같으며, i번째 줄의 i번째 수는 항상 0이다.

첫째 줄에 도시 0에서 1을 가는데 가장 빠른 시간을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.