Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3971
Berth Allocation

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 ti, 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 bi ∈ {1, 2, ..., n}, as well on the starting time of berthing, denoted by si ≥ 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 bi = bj, then either si + ti, bisj or sj + tj, bjsi must be satisfied. Your task is to help Owen to minimize the total completion time of the vessels, i.e., to minimize

sum_{i=1}^m (s_i + t_{i, b_i})

Figure 1. An illustrated example, with a quay of n = 5 berths, m = 7 vessels, where two vessels are waiting outside the quay.

Input

First 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 ti, 1, ti, 2, ..., and ti, n (ti, j ≤ 1000) for i = 1, 2, 3, ..., m.

Output

For each case, output one integer, the minimum total completion time of all the vessels.

Sample Input

1
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 Output

11

Source: ACM Collegiate Programming Contest 2017 (Hong Kong)
Submit    Status