
ZOJ Problem Set  3971
In a container terminal, such as the Hong Kong Container Terminal, the bottleneck of the traffic is often at the quay. Therefore, the terminal operator has to allocate a limited number of berths of the quay to vessels in an efficient way. As illustrate in Figure 1 below, consider a container terminal of n berths and m vessels arrived, where each vessel i (for i = 1, 2, ..., m) requires a berth to load and unload containers, and the handling time is t_{i, j} if berth j (for j = 1, 2, ..., n) is allocated to vessel i. For each vessel i = 1, 2, ..., m, the terminal manager, Owen, needs to decide on the berth, denoted by b_{i} ∈ {1, 2, ..., n}, as well on the starting time of berthing, denoted by s_{i} ≥ 0. It must be satisfied that no two vessels are allowed to occupy the same berth simultaneously, i.e., for any two different vessels i and j, if b_{i} = b_{j}, then either s_{i} + t_{i, bi} ≤ s_{j} or s_{j} + t_{j, bj} ≤ s_{i} must be satisfied. Your task is to help Owen to minimize the total completion time of the vessels, i.e., to minimize Figure 1. An illustrated example, with a quay of n = 5 berths, m = 7 vessels, where two vessels are waiting outside the quay. InputFirst line of the input is an integer T indicating the number of test cases. For each case, the first line contains two integers n and m (1 ≤ n ≤ 50, 1 ≤ m ≤ 200). Each of the following m lines contains n positive integers representing vessel i's handling times t_{i, 1}, t_{i, 2}, ..., and t_{i, n} (t_{i, j} ≤ 1000) for i = 1, 2, 3, ..., m. OutputFor each case, output one integer, the minimum total completion time of all the vessels. Sample Input1 5 7 1 2 3 4 5 2 1 3 4 5 2 3 1 4 5 2 3 4 1 5 2 3 4 5 1 2 2 2 2 2 2 2 2 2 2 Sample Output11 Source: ACM Collegiate Programming Contest 2017 (Hong Kong) 