Kwiaciarnia

Jesteś właścicielem kwiaciarni i przygotowujesz okno wystawowe. Dysponujesz F bukietami kwiatów - każdy innego rodzaju. Masz też do dyspozycji co najmniej tyle samo wazonów, ustawionych w rzędzie na parapecie okna. Wazony są przymocowane na stałe do parapetu i ponumerowane kolejno od 1 do V, gdzie V jest liczbą wazonów. Skrajnie lewy wazon ma numer 1, a skrajnie prawy ma numer V. Bukiety są jednoznacznie ponumerowane od 1 do F. Te numery są ważne z następującego powodu - określają one kolejność występowania bukietów w wazonach. Dla i<j bukiet nr i musi zawsze znajdować się w wazonie położonym na lewo od wazonu, w którym znajduje się bukiet nr j. Np., jeśli azalie mają nr 1, begonie mają nr 2, a cyprysy mają nr 3, to ich bukiety muszą znajdować się w wazonach właśnie w takim porządku - wazon z azaliami musi być na lewo od wazonu z begoniami, a ten na lewo od wazonu z cyprysami. Jeśli mamy więcej wazonów niż bukietów, to nadmiarowe wazony pozostają puste. W każdym wazonie może znajdować się co najwyżej jeden bukiet kwiatów.

Wazony (tak jak bukiety kwiatów) mają swoje charakterystyki. Wkładając bukiet kwiatów do wazonu uzyskujemy określony efekt estetyczny, wyrażany liczbą całkowitą. W tabeli poniżej przedstawiono liczby wyrażające przykładowe efekty estetyczne. W przypadku gdy wazon jest pusty daje to efekt estetyczny równy 0.

Zgodnie z powyższą tabelą, azalie wyglądałyby wspaniale w wazonie nr 2, a strasznie w wazonie nr 4.

Dla osiągnięcia najlepszego efektu musisz umieścić bukiety w wazonach, zachowując podany porządek i maksymalizując sumę efektów estetycznych. Jeśli jest kilka takich rozmieszczeń, to każde z nich jest dopuszczalne. Musisz znaleźć jedno z nich.

Założenia

• , gdzie F jest liczbą bukietów kwiatów. Bukiety są ponumerowane od 1 do F.
• , gdzie V jest liczbą wazonów.
• , gdzie A_ij jest efektem estetycznym umieszczenia i-go bukietu w j-tym wazonie.

Wejście

Nazwą pliku wejściowego jest: flower.inp.

• Pierwszy wiersz zawiera dwie liczby: F, V.
• Kolejnych F wierszy ma następującą postać: każdy z nich zawiera V liczb całkowitych - liczba A_ij jest j-tą liczbą w (i+1)-ym wierszu.

Wyjście

Plik wyjściowy flower.out musi być plikiem tekstowym i zawierać dwa wiersze:

• Pierwszy wiersz zawiera sumę efektów estetycznych twojego rozmieszczenia.
• Drugi wiersz musi zawierać to rozmieszczenie w postaci ciągu F liczb całkowitych, w którym k-ty element jest numerem wazonu zawierającego bukiet nr k.

Przykład

flower.inp:

3 5 
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

flower.out:

53
2 4 5

Ocena

Ograniczenie na czas działania programu wynosi 2 sekundy. Nie można otrzymać części punktów za pojedynczy test.