Conference Rides

There are $n$ attendees at a conference, numbered $1$ through $n$. Each of the first $m$ attendees (numbered $1$ through $m$) has a car to drive home after the event. The remaining $n - m$ attendees have no car and must get a ride home from the first $m$ attendees. Each attendee with a car can pick up at most one other attendee from attendees $m + 1$ through $n$, drive them home, and then drive to their own home.

You are given a distance matrix $D$ of size $(n+1) \times (n+1)$ covering the $n$ attendees' homes and the conference hall. For $1 \le i \le n$, location $i$ is the home of attendee $i$, and location $n+1$ is the conference hall. $D[i][j]$ is the estimated travel time from location $i$ to location $j$.

Assign drivers to passengers so that the time until every attendee has reached home is minimized.

The input starts with a line containing two integers $n$ and $m$ ($1 \le n \le 500$, $1 \le m \le n$). It is guaranteed that $2m \ge n$.

The next $n+1$ lines each contain $n+1$ integers. The $j$th number on the $(i+1)$th line is $D[i][j]$ ($0 \le D[i][j] \le 10^8$). $D[i][i] = 0$ for all $i$, and $D[i][k] \le D[i][j] + D[j][k]$ for all $i$, $j$, $k$. $D$ is not necessarily symmetric.

On the first line, print the minimum time until all attendees have arrived home.

On each of the next $m$ lines, print a non-negative integer $t_i$ for $1 \le i \le m$. If $t_i = 0$, attendee $i$ drives directly home without picking anyone up. If $t_i > 0$, attendee $i$ picks up attendee $t_i$, drives them home, and then drives home. Each attendee without a car must be picked up by exactly one car.