Dom mody kapitana Mambeksa przygotowuje się do pokazu swej najnowszej kolekcji "Lato 2005" złożonej z M kreacji. Kapitan przydzielił wszystkim kreacjom unikalne numery z zakresu 1, ..., M i postanowił, że kreacje będą prezentowane w kolejności określonej przydzielonymi numerami. Kapitan pragnie osiągnąć sukces i liczy na masowe zamówienia swych kreacji, a co za tym idzie na ogromne zyski, dlatego do pokazu wynajął najlepsze modelki ze świata mody. Niestety każda modelka na wstępie postawiła warunek, że zaprezentuje tylko jedną kreację co rozczarowało trochę kapitana. Kolejne rozczarowanie pojawiło się w trakcie próbnego pokazu. Otóż okazało się, że nie każda modelka równie dobrze prezentuje się we wszystkich kreacjach. Niektóre modelki po prostu nie nadają się do prezentacji wybranych kreacji, gdyż efekt jest odwrotny do zamierzonego. Wszystko to zmusza kapitana do wynajęcia N modelek, gdzie N musi być równe co najmniej liczbie kreacji M. Aby nad wszystkim zapanować, kapitan zatrudnionym modelkom przydzielił unikalne numery z zakresu 1, ..., N oraz postanowił, że modelki będą pojawiać się na wybiegu w określonej kolejności - na wybiegu nie będzie mogła pojawić się modelka o numerze mniejszym od numerów modelek, które były wcześniej na wybiegu.
Aby osiągnąć oczekiwany efekt pokazu kapitan przeprowadził próbny pokaz podczas którego każda z modelek zaprezentowała się we wszystkich kreacjach. Po próbie kapitan dokonał oceny wrażenia jakie na nim wywarła każda modelka w poszczególnych kreacjach. Im wystawiona ocena jest wyższa tym większe wrażenie zostało wywarte na kapitanie.
Mając oceny z próbnego pokazu kapitan postanowił zaplanować pokaz, tj. przydzielić każdą z kreacji do określonej modelki. Kapitan chce dokonać przydziału w taki sposób aby osiągnąć maksymalne wrażenie podczas pokazu. Wrażenie pokazu jest liczone jako suma wrażeń wywieranych przez poszczególne modelki na wybiegu. Ponieważ liczba zatrudnionych modelek może być większa od liczby kreacji, dlatego część modelek nie zaprezentuje się na wybiegu. Twoim zadaniem jest pomóc kapitanowi pisząc program, który wyznaczy przyporządkowanie każdej kreacji do określonej modeli w taki sposób, aby osiągnąć maksymalne wrażenie podczas pokazu.
W pierwszym wierszu wejścia znajduje się jedna liczba K będąca liczbą zestawów danych.
Opis jednego zestawu danych składa się z M+1 wierszy i ma następującą postać:
M N
w_11 w_12 ... w_1N
w_21 w_22 ... w_2N
..................
w_M1 w_M2 ... w_MN
Pierwszy wiersz zawiera dwie liczby całkowite M (1 ≤ M ≤ 500), N (M ≤ N ≤ 500) określające odpowiednio liczbę kreacji prezentowanych podczas pokazu oraz liczbę zatrudnionych modelek. Kolejnych M wierszy zawiera N liczb całkowitych w_ij (-250 ≤ w_ij ≤ 250) określających ocenę wrażenia wywartego przez j-tą modelkę prezentującą i-tą kreację.
Dane wyjściowe składają się z K wierszy. Jeden wiersz odpowiada jednemu zestawowi danych wejściowych i zawiera liczbę całkowitą określającą maksymalne wrażenie jakie można osiągnąć podczas pokazu.
4
4 7
-9 5 3 -7 -6 -5 7
4 8 -3 2 -2 0 3
1 6 4 5 -5 -3 8
6 4 9 3 -2 -4 -6
3 5
-9 -8 3 6 7
9 -2 2 -1 1
1 8 5 3 -3
6 6
3 -2 4 2 1 -3
2 -1 4 7 0 5
7 3 5 3 -6 2
-3 2 -1 1 3 5
4 2 5 3 -3 -4
7 -5 -3 3 2 4
5 7
1 4 2 -4 3 -1 5
4 -2 -7 -3 5 3 -3
6 7 -5 -7 -6 5 4
2 -4 5 -6 -8 7 -1
7 3 7 -4 -3 4 -2
6
-1
9
0