Description:


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

Input:


第一行有两个m,n,表示技术人员数与顾客数。 接下来n行,每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

Output:


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

Sample Input:


Sample Output:

HINT:


数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

题解:


看到这个题目的数据范围以及题目描述可以猜到这是费用流的题。

但是建模有一点难。
考虑如果第k个维修人员修了a辆车,那么第一个修车的人所用的时间需要乘以a,第二个就乘以a-1以此类推。
我们可以左边用n个点代表n辆车,右边用n*m个点,其中第i列第j个点表示第i个维修人员维修的第j辆车。
然后连边,对于第i辆车和右边第j列第k个点连上费用等于时间乘上k的边,然后源点向左边的点,右边的点向汇点连边,费用为0。

然后流量都为1。

就是这样。