Hide

Problem M
Dog Trouble

Yraglac is running a daycare service for dogs. He has N dogs and he would like to take them on a walk. However, before he can walk the dogs, he needs to feed them first.

Yraglac has M feeding bowls. Because the dogs are very well trained, he can instruct a dog to eat from a specific bowl, but he can’t instruct multiple dogs to eat from the same bowl. A dog is considered to be fed after eating from a single bowl. However, different dogs may have different food preferences, so they may eat from the same food bowl at different speeds.

As you know, dogs get impatient if they have to wait for long periods of time. Therefore, Yraglac wants to minimize the total amount of time that dogs spend waiting. More formally, suppose t is the longest amount of time in seconds that any dog spent eating. Yraglac wants to minimize T=i=1Ntti, where ti is the time in seconds that the ith dog spends eating.

Input

The first line contains integers N and M, where 2NM50.

Each of the next N lines of the input contains M integers each. The jth integers on the ith line denotes the tij, the amount of time that the ith dog will spend on eating food from the jth bowl. Note that 1tij200.

Output

Output T, the minimum total waiting time in seconds.

Sample Input 1 Sample Output 1
2 3
2 100 10
100 1 10
0
Sample Input 2 Sample Output 2
3 3
100 20 30
10 90 80
99 90 98
12
Hide

Please log in to submit a solution to this problem

Log in