Conference Rides

문제

There are $nn$ attendees in a conference, numbered $11$ through $nn$. Each of the first $mm$ attendees (numbered $11$ through $mm$) has a car to drive home after the event. The remaining $n-mn\; -\; m$ attendees who do not have a car, are going to get a ride to their homes with the help of the first $mm$ attendees. Each of the first $mm$ attendees can pick up at most one other attendee (from attendees $m+1m\; +\; 1$ to $nn$) and drive them to their house before going to their own home. You are given the distance matrix $DD$ of the $n+1n\; +\; 1$ locations (the conference hall and $nn$ 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 $DD$ is an $(n+1)\times (n+1)(n+\; 1)\; \backslash times\; (n+\; 1)$ matrix where $D[i][j]D[i][j]$ denotes the estimated time of transportation from location $ii$ to location $jj$. Location $ii$ (for $1\le i\le n1\; \backslash le\; i\; \backslash le\; n$) denotes the home of the $ii$^th attendee and the conference hall is positioned at location $n+1n\; +\; 1$.

입력

The input starts with a line containing two integers $nn$ and $mm$, ($1\le n\le 5001\; \backslash le\; n\; \backslash le\; 500$ and $1\le m\le n1\; \backslash le\; m\; \backslash le\; n$). It is guaranteed that $2m\ge n2m\; \backslash ge\; n$.

The following $n+1n+1$ lines specify the distance matrix $DD$, each containing $n+1n+1$ integers. The $jj$^th number from the $i+1i\; +\; 1$^th line of the input (for $1\le i,j\le n+11\; \backslash le\; i,\; j\; \backslash le\; n\; +\; 1$) specifies $D[i][j]D[i][j]$ ($0\le D[i][j]\le {10}^{8}0\; \backslash le\; D[i][j]\; \backslash le\; 10^8$). It is guaranteed that $D[i][k]\le D[i][j]+D[j][k]D[i][k]\; \backslash le\; D[i][j]\; +\; D[j][k]$ for any $1\le i,j,k\le n+11\; \backslash le\; i,\; j,\; k\; \backslash le\; n\; +\; 1$, and also $D[i][j]=0D[i][j]\; =\; 0$ for $i=ji\; =\; j$, but $D[i][j]D[i][j]$ is not necessarily equal to $D[j][i]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 $mm$ lines, each line $ii$ (for $1\le i\le m1\; \backslash le\; i\; \backslash le\; m$) should contain a single non-negative integer $t_{i}t\_i$, denoting the driving schedule of the $ii$^th attendee. If $t_i=0t\_i\; =\; 0$, the attendee drives directly to their home without picking up any other attendees. Otherwise ($t_i>0t\_i\; >\; 0$), the $ii$^th attendee picks up the attendee $t_{i}t\_i$ and takes them to their home before driving to their own home. Each attendee must be transferred by exactly one car.