컨퍼런스 카풀

컨퍼런스에 참가자가 $n$명 있으며, $1$번부터 $n$번까지 번호가 붙어 있다. 처음 $m$명($1$번부터 $m$번까지)은 행사가 끝난 뒤 집에 갈 차가 있다. 나머지 $n - m$명은 차가 없어서 처음 $m$명의 도움을 받아 집에 간다. 차가 있는 참가자는 $m + 1$번부터 $n$번까지 참가자 중 최대 한 명을 태워 집까지 데려다준 뒤, 자기 집으로 갈 수 있다.

참가자들의 집과 컨퍼런스 장소를 포함한 $(n+1) \times (n+1)$ 크기의 거리 행렬 $D$가 주어진다. $1 \le i \le n$인 위치 $i$는 $i$번 참가자의 집이고, 위치 $n+1$은 컨퍼런스 장소다. $D[i][j]$는 위치 $i$에서 위치 $j$까지 이동하는 예상 시간이다.

모든 참가자가 집에 도착할 때까지 걸리는 시간이 최소가 되도록 차가 있는 참가자와 차가 없는 참가자를 짝지어라.

첫 줄에 정수 $n$과 $m$이 주어진다($1 \le n \le 500$, $1 \le m \le n$). $2m \ge n$이 보장된다.

이어서 $n+1$개의 줄에 각각 $n+1$개의 정수가 주어진다. $(i+1)$번째 줄의 $j$번째 수가 $D[i][j]$다($0 \le D[i][j] \le 10^8$). 모든 $i$에 대해 $D[i][i] = 0$이고, 모든 $i$, $j$, $k$에 대해 $D[i][k] \le D[i][j] + D[j][k]$가 성립한다. $D$는 대칭이라고 보장되지 않는다.

첫 줄에 모든 참가자가 집에 도착하는 데 걸리는 최소 시간을 출력한다.

이어서 $1 \le i \le m$인 각 줄에 음이 아닌 정수 $t_i$를 출력한다. $t_i = 0$이면 $i$번 참가자는 아무도 태우지 않고 바로 집으로 간다. $t_i > 0$이면 $i$번 참가자는 $t_i$번 참가자를 태워 집까지 데려다준 뒤 자기 집으로 간다. 차가 없는 참가자는 정확히 한 대의 차에 타야 한다.