有一個賣貨郎要旅行 \(n\) 個城市做生意並且回到他的家，由於路途遙遠，他希望走的路程總和越短越好，希望你幫他規劃最短路線。 這 \(n\) 個城市由 \(0\)\(None\)n-1\( 編號，他的家在編號 \)m\( 的城市。對任意兩個城市 \)i\( 與 \)j\(，已知兩者之間的距離是 \)d[i][j]~，而且繞經第三地的路程絕對不會更短。

輸入格式

第一行有兩個正整數 \(n\) 與 \(m\)。 接下來 \(n\) 行每行 \(n\) 個非負整數是矩陣 \(d[i][j]\) 的內容，順序由上而下，由左而右，\(i\) 從 \(0\)～\(n-1\)，\(j\) 從 \(0\)～\(n-1\)。\(n < 17\)， 假設 \(d[i][j]=d[j][i]\), \(d[i][i]=0\), 且 \(d[i][j] \leq 100\)。

輸出格式

最短總路程。

範例輸入 1

4 0
0 1 1 2
1 0 1 2
1 1 0 1
2 2 1 0

範例輸出 1

5

範例輸入 2

4 2
0 2 1 1
2 0 1 1
1 1 0 2
1 1 2 0

範例輸出 2

4