P2053 [SCOI2007] Car Repair

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.

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 the minimum average waiting time, accurate to $2$ decimal places.

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