33199번 - Conference Rides 스페셜 저지다국어

문제

There are $n$ attendees in 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 who do not have a car, are going to get a ride to their homes with the help of the first $m$ attendees. Each of the first $m$ attendees can pick up at most one other attendee (from attendees $m + 1$ to $n$) and drive them to their house before going to their own home. You are given the distance matrix $D$ of the $n + 1$ locations (the conference hall and $n$ attendees’ homes). Find a way for attendees with cars to drive the attendees without cars home, such that the time it takes for all attendees to arrive at their homes is minimized. The distance matrix $D$ is an $(n+ 1) \times (n+ 1)$ matrix where $D[i][j]$ denotes the estimated time of transportation from location $i$ to location $j$. Location $i$ (for 1ドル \le i \le n$) denotes the home of the $i$^th attendee and the conference hall is positioned at location $n + 1$.

입력

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

The following $n+1$ lines specify the distance matrix $D,ドル each containing $n+1$ integers. The $j$^th number from the $i + 1$^th line of the input (for 1ドル \le i, j \le n + 1$) specifies $D[i][j]$ (0ドル \le D[i][j] \le 10^8$). It is guaranteed that $D[i][k] \le D[i][j] + D[j][k]$ for any 1ドル \le i, j, k \le n + 1,ドル and also $D[i][j] = 0$ for $i = j,ドル but $D[i][j]$ is not necessarily equal to $D[j][i]$.

출력

In the first line of output, print the minimum time it takes for all attendees to arrive at their homes. In the next $m$ lines, each line $i$ (for 1ドル \le i \le m$) should contain a single non-negative integer $t_i,ドル denoting the driving schedule of the $i$^th attendee. If $t_i = 0,ドル the attendee drives directly to their home without picking up any other attendees. Otherwise ($t_i > 0$), the $i$^th attendee picks up the attendee $t_i$ and takes them to their home before driving to their own home. Each attendee must be transferred by exactly one car.

제한

힌트