Space Probe

Interview

Time limit1sMemory limit512 MB

Summary

Given travel times between N planets and a start planet, find the shortest route that visits every planet, with no need to return to the start.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Graph, Brute force
Solved: No attempts yet

Problem

The space probe ana is launched to explore a planetary system. You want to compute the minimum time needed to explore every planet. The input gives the number of planets ana will explore, the position of the planet from which ana is launched, and the travel times between planets as a two-dimensional matrix. Planet positions start at 0, and 0 means the planet at index 0 in the matrix. The element in row i and column j of the matrix is the time needed to reach planet j from planet i. When i equals j, the value is always 0. Compute the minimum time needed to explore every planet.

After exploring, ana does not need to return to the starting planet, and it may revisit planets it has already visited.

Input

The first line gives the number of planets N and the position K of the planet from which ana is launched. (2 ≤ N ≤ 10, 0 ≤ K < N)

The next N lines give the travel time Tij between each pair of planets, with N values per line separated by spaces. (0 ≤ Tij ≤ 1000)

Output

Print the minimum time needed to explore every planet.

Examples2

Example 1
Input
```
3 0
0 30 1
1 0 29
28 1 0
```
Expected output
```
2
```

Example 2

Input

Expected output