P2050 [NOI2012] Food Festival

To welcome students from all over the country, CZ City is hosting a grand food festival. As a foodie who loves trying new things, Xiao M would not miss this feast. He quickly tasted all the foods at the festival. However, the desire to try new dishes is hard to satisfy. Although all dishes are delicious and the chefs cook fast, Xiao M still feels it is unbearable if there is no dish on his table that has already appeared on someone else’s table. So he begins to study the problem of cooking order, that is, arranging a cooking sequence so that the students’ waiting time is minimized. Xiao M finds that there are $n$ different types of dishes. Each time they order, each student may choose exactly one dish. There are $m$ chefs to prepare these dishes. After all students finish ordering, the dish-making tasks are assigned to the chefs. Then all chefs start cooking simultaneously. The chefs follow the required sequence and can cook only one serving at a time. In addition, Xiao M finds another interesting fact — although the $m$ chefs can all make all $n$ types of dishes, for the same dish, different chefs may take different amounts of time. He numbers the dishes $1, 2, \ldots, n$ and the chefs $1, 2, \ldots, m$, and lets $t_{i,j}$ be the time for chef $j$ to make dish $i$. Xiao M defines the waiting time of each student as the duration from when all chefs start cooking until that student’s serving is completed. In other words, if a student’s dish is the $k$-th dish made by some chef, then the student’s waiting time is the sum of the times of that chef’s first $k$ dishes. The total waiting time is the sum of all students’ waiting times. Now Xiao M knows all the ordering information — there are $p_i$ students who ordered dish $i$ for $i = 1, 2, \ldots, n$. He wants to know the minimum possible total waiting time.

The first line contains two positive integers $n$ and $m$, the number of dish types and the number of chefs. The second line contains $n$ positive integers; the $i$-th number is $p_i$, the number of students who ordered dish $i$. Then there are $n$ lines, each containing $m$ non-negative integers. In these $n$ lines, the $j$-th number on the $i$-th line is $t_{i,j}$, the time needed for chef $j$ to make dish $i$. In the input file, adjacent numbers on each line are separated by a single space, and there are no extra spaces at the end of any line.

Output a single line containing one integer: the minimum total waiting time.

Chef $1$ first makes $1$ serving of dish $2$, then makes $2$ servings of dish $1$. The waiting times of the $3$ students who ordered these $3$ servings are $3$, $3+5=8$, and $3+5+5=13$. Chef $2$ first makes $1$ serving of dish $1$, then makes $1$ serving of dish $3$. The waiting times of the $2$ students who ordered these $2$ servings are $7$ and $7+9=16$. The total waiting time is $3+8+13+7+16=47$. Although dishes $1$ and $3$ are faster if made by chef $1$, the total waiting time would be longer if all these dishes were made by chef $1$. If, as above, we reassign $1$ serving of dish $1$ and $1$ serving of dish $3$ to chef $2$, then chef $2$ will not be idle, and the total waiting time is shorter. It can be proved that there is no better ordering and assignment. For each test set, the values of $n$, $m$, and $p$ are as follows: - Test point $1$: $n = 5$, $m = 5$, $p = 10$. - Test point $2$: $n = 40$, $m = 1$, $p = 400$. - Test point $3$: $n = 40$, $m = 2$, $p = 300$. - Test point $4$: $n = 40$, $m = 40$, $p = 40$. - Test point $5$: $n = 5$, $m = 40$, $p = 100$. - Test point $6$: $n = 10$, $m = 50$, $p = 200$. - Test point $7$: $n = 20$, $m = 60$, $p = 400$. - Test point $8$: $n = 40$, $m = 80$, $p = 600$. - Test point $9$: $n = 40$, $m = 100$, $p = 800$. - Test point $10$: $n = 40$, $m = 100$, $p = 800$. Constraints for $100\%$ of the testdata: $n \leq 40$, $m \leq 100$, $p \leq 800$, $t_{i,j} \leq 1000$ (where $p = \sum p_i$). Translated by ChatGPT 5