C1343 [SCOI2007]修车

内存限制:256 MB 时间限制:1000 ms

题目描述

同一时刻有 $N$ 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 $M$ 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 $M$ 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。

说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入格式

第一行有两个 $m,n$,表示技术人员数与顾客数。

接下来 $n$ 行,每行 $m$ 个整数。

第 $i+1$ 行第 $j$ 个数表示第 $j$ 位技术人员维修第 $i$ 辆车需要用的时间 $T$。

输出

最小平均等待时间,答案精确到小数点后 $2$ 位。

样例

样例输入 1

2 2 3 2 1 4

样例输出 1

1.50

提示

数据范围:

$2 \le M \le 9,1 \le N \le 60$

$1 \le T \le 1000$