一次会议有 $n$ 名参会者，编号为 $1$ 到 $n$。前 $m$ 名参会者（编号为 $1$ 到 $m$）在活动结束后有车可以开车回家。剩下的 $n - m$ 名没有车的参会者将在前 $m$ 名参会者的帮助下乘车回家。前 $m$ 名参会者中的每人最多可以顺路接送一名其他参会者（在编号为 $m + 1$ 到 $n$ 的参会者中），将其送回家后再开回自己家。

现给出 $n + 1$ 个位置（会议厅和 $n$ 名参会者的家）之间的距离矩阵 $D$。请为有车的参会者安排一种送无车参会者回家的方案，使得所有参会者都回到家所需的时间（即所有人中最后到家者的到家时间）最小。

距离矩阵 $D$ 是一个 $(n + 1) \times (n + 1)$ 的矩阵，其中 $D[i][j]$ 表示从位置 $i$ 到位置 $j$ 的预估交通时间。位置 $i$（对于 $1 \le i \le n$）表示第 $i$ 名参会者的家，会议厅位于位置 $n + 1$。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 500$ 且 $1 \le m \le n$）。保证 $2m \ge n$。

接下来的 $n + 1$ 行定义了距离矩阵 $D$，每行包含 $n + 1$ 个整数。输入中第 $i + 1$ 行的第 $j$ 个数（对于 $1 \le i, j \le n + 1$）表示 $D[i][j]$（$0 \le D[i][j] \le 10^8$）。保证对于任意 $1 \le i, j, k \le n + 1$，均满足三角不等式 $D[i][k] \le D[i][j] + D[j][k]$，且当 $i = j$ 时 $D[i][j] = 0$，但 $D[i][j]$ 不一定等于 $D[j][i]$。

输出格式

输出的第一行，打印所有参会者都回到家所需的最短时间。

在接下来的 $m$ 行中，第 $i$ 行（对于 $1 \le i \le m$）应包含一个非负整数 $t_i$，表示第 $i$ 名参会者的行车路线。

• 如果 $t_i = 0$，表示该参会者直接开车回家，不接送任何其他参会者。
• 否则（$t_i > 0$），表示第 $i$ 名参会者先去接参会者 $t_i$ 并将其送回家，然后再开车回到自己家。

每个（没车的）参会者必须恰好被一辆车送回家。

样例

输入样例 1

3 2
0 1 1 2
2 0 1 3
4 2 0 4
4 3 2 0

输出样例 1

4
0
3