Description

At time $0$, $N$ customers arrive at an auto repair center with their cars.

There are $M$ technicians in the center, and the time required by different technicians to repair different cars may differ.

Arrange which cars each of the $M$ technicians repairs and in what order, so that the average waiting time of the customers is minimized.

Explanation: A customer's waiting time is the time from when they deliver the car to the repair center until the repair is completed.

Input Format

The first line contains two integers $M, N$, the number of technicians and the number of customers.

The next $N$ lines each contain $M$ integers. In row $i+1$, the $j$-th number denotes the time $T_{i, j}$ needed for technician $j$ to repair car $i$.

Output Format

Output the minimum average waiting time, accurate to $2$ decimal places.

2 2
3 2
1 4

1.50

Hint

Constraints: For $100\%$ of the testdata, $2 \le M \le 9$, $1 \le N \le 60$, $1 \le T \le 10^3$.

Translated by ChatGPT 5