POLSKI SPOJ

Jeśli chcesz kupić n przedmiotów, ale każdy w innym sklepie, to ile najmniej pieniędzy potrzebujesz, aby zdobyć wszystkie przedmioty?

Wejście

W pierwszym wierszu t – liczba zestawów danych (t ≤ 25000). Każdy zestaw składa się na początku z jednej liczby naturalnej n (1 ≤ n ≤ 100) oznaczającej liczbę przedmiotów i sklepów. W kolejnych n wierszach, n liczb całkowitych (nieujemnych, nie większych niż 10⁶) oznaczających ceny poszczególnych przedmiotów w poszczególnych sklepach, np. druga liczba w czwartym wierszu oznacza ile kosztuje czwarty przedmiot w drugim sklepie. Pliki wejściowe nie przekraczają 6 MB.

Wyjście

Dla każdego zestawu danych należy wypisać najmniejszą kwotę, za którą kupimy wszystkie n przedmiotów uwzględniając założenie, że można kupić co najwyżej jedną rzecz w jednym sklepie.

Przykład

Wejście:

2
3
1 9 9
9 1 9
9 9 1
4
5 8 2 6
1 4 1 4
3 3 6 6
7 5 4 4

Wyjście:

3
10