National Olympiad in Informatics, China, 2012
To welcome students from all across the nation, City CZ is specially hosting a grand food festival.
Being a food fanatic who loves to try new flavors, little M obviously does not want to miss this feast. Going there, he quickly was able to sample lots of the festival's great foods. Yet, it is still hard to satisfy the appetite of a true gastronome, even if the dishes are very tasty and the kitchen is very efficient. Little M still thinks that not having dishes which are already on someone else's table is an unbearable feeling. So, little M started to investigate issues relating to the order in which dishes are prepared, hoping to create an efficient system that minimizes the waiting time of students.
Little M noticed that the food festival contains varieties of delicacies. When ordering each time, each student can select one of these varieties. There are a total of chefs to prepare these dishes. After all of the students have ordered, the tasks of preparing the dishes will assigned to each of the chefs. Then, each chef will simultaneously start to cook. The chefs will follow the required order when they prepare the dishes, and each time can only make a portion for one person.
Other than this, little M also made an interesting observation – even though these chefs all know how to fully prepare all varieties of delicacies, different chefs may require different amounts of time to prepare the same dish. He numbered the types of delicacies from to , and the chefs from to , denoting the time it takes for -th chef to prepare the -th delicacy as .
Little M will consider each student's waiting time to be from when all chefs start to cook to when their own dish is fully prepared. In other words, if a student's ordered dish is the -th delicacy to be prepared by some chef, then their waiting time is the sum of the preparation times of the first dishes that this chef prepares. The total waiting time is the sum of the waiting times among all of the students.
Now, little M has the orders of each and every student – there are students who ordered the -th type of delicacy (for ). He would like to know the minimum possible total waiting time.
The first line of input contains two positive integers and ,
representing the number of varieties of delicacies and chefs,
Line contains positive integers , where is the number of students who ordered the -th delicacy.
For the following lines, each line contains nonnegative integers. The -th integer on the -th line will be , the time it takes for the -th chef to prepare the -th delicacy.
All adjacent numbers on the same line will be separated by a single space, and there will be no trailing spaces on any line.
Output one line containing a single integer, the smallest possible total waiting time.
3 2 3 1 1 5 7 3 6 8 9
Chef first prepares order of delicacy , then prepares orders of
delicacy . The waiting times of the students who ordered these
dishes are respectively , , and .
Chef first prepares order of delicacy , then prepares order of delicacy . The waiting times of the students who ordered these dishes are respectively and .
The total waiting time is .
Although delicacies and are best cooked by chef , if these are both cooked by chef , then the total waiting time will actually be longer. If the solution described above is followed where order of delicacy and order of delicacy is tasked to chef , then chef will not be idle, reducing the waiting time.
It can be proven that no solution exists which is more optimal.
For of test cases, , and (where and the total number of ordering students).
The following additional constraints for , , and will hold.