# Berth Allocation

Time Limit: 2 Seconds

Memory Limit: 65536 KB

## Description

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


None

None