描述

农夫约翰（FJ）将他的 $K$（$1 \leq K \leq 30$）台挤奶机搬到了牧场中的 $C$（$1 \leq C \leq 200$）头奶牛之间。奶牛和挤奶机之间通过一系列长度不等的路径相连。挤奶机的位置用编号 $1$ 到 $K$ 表示，奶牛的位置用编号 $K+1$ 到 $K+C$ 表示。

每台挤奶机每天最多可以“处理” $M$（$1 \leq M \leq 15$）头奶牛。编写一个程序，为每头奶牛分配一台挤奶机，使得走得最远的奶牛所走的路程尽可能短（同时确保挤奶机不会超负荷工作）。所有输入数据保证至少存在一种合法的分配方案。奶牛在前往挤奶机的过程中可以经过多条路径。

输入格式

• 第 1 行：三个用空格分隔的整数 $K$、$C$ 和 $M$。
• 第 2 行及之后：接下来的 $K+C$ 行，每行包含 $K+C$ 个用空格分隔的整数，描述各实体之间的距离。输入是一个对称矩阵。第 2 行表示挤奶机 1 到其他各实体的距离；第 3 行表示挤奶机 2 到其他各实体的距离，依此类推。直接相连的实体之间的距离为正整数且不超过 $200$，未直接相连的实体距离为 $0$。实体到自身的距离（对角线上的数字）也为 $0$。如果 $K+C > 15$，则每行会分成连续的 15 个数字一组，剩余部分另起一行继续显示。每行数据从新的一行开始。

输出格式

一行，包含一个整数，表示走得最远的奶牛的最小可能总距离。

输入数据 1

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

输出数据 1

2  

来源

USACO 2003 美国公开赛