봉인실에는 0번부터 N-1번까지 번호가 붙은 봉인 문양이 있다. 작업자는 처음에 K번 문양 앞에 서 있으며, 모든 문양을 적어도 한 번씩 활성화해야 한다.

한 문양에서 다른 문양으로 작업 위치를 옮길 때 필요한 시간이 행렬로 주어진다. 행렬의 i행 j열 값은 i번 문양에서 j번 문양으로 옮기는 데 걸리는 시간이다. 같은 문양으로 옮기는 시간은 항상 0이다.

이미 활성화한 문양을 다시 지나가도 되며, 모든 문양을 활성화한 뒤 처음 문양으로 돌아올 필요는 없다. 모든 문양을 활성화하는 데 필요한 최소 시간을 구하시오.

입력

첫 번째 줄에는 문양의 개수 N과 시작 문양의 번호 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N줄에 걸쳐 각 문양 사이의 이동 시간 Tij가 N개씩 공백으로 구분되어 주어진다. (0 ≤ Tij ≤ 1000)

출력

모든 문양을 활성화하기 위한 최소 시간을 출력한다.

예제 입력 1

3 0
0 30 1
1 0 29
28 1 0

예제 출력 1

2

예제 입력 2

4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

예제 출력 2

74