[placeholder] rất lười vận động. Cậu suốt ngày ngồi ở nhà chơi điện tử. Một ngày, mẹ của [placeholder] rút dây máy tính, và bắt cậu ra ngoài đi dạo 1 vòng.

Nhà của [placeholder] nằm ở đỉnh $1$ trong một đồ thị đầy đủ có hướng gồm $n$ đỉnh. Các cạnh của đồ thị có trọng số. [placeholder] muốn tìm đi thăm $k-1$ người bạn. Vì rất lười nên [placeholder] muốn chuyến đi dạo ngắn nhất có thể.

Bạn hãy giúp [placeholder] tìm một chu trình đơn giản có độ dài $k$ có tổng trọng số các cạnh là nhỏ nhất.

Input

Dòng đầu tiên chứa 2 số $n$, $k$, số đỉnh của đồ thị và độ dài chu trình cần tìm ($n\le 50$, $k\le min(n,8),k$ chẵn).

$n$ dòng tiếp theo, mỗi dòng chứa $n$ số $a_{i,j}$, độ dài cạnh từ đỉnh $i$ đến đỉnh $j$ ($1\le a_{i,j}\le 100000,a_{i,i}=0$)

Output

Dòng đầu chứa số $s$ - độ dài của chu trình ngắn nhất. Dòng tiếp theo chứa $k$ số - các đỉnh trên chu trình. Đỉnh đầu tiên của chu trình phải là đỉnh $1$.

Sample Input 1

5 4
0 2 5 4 2 
9 0 5 3 7 
1 6 0 4 3 
9 7 8 0 5 
1 5 7 3 0 

Sample Output 1

11
1 2 3 5