W lewym górnym rogu prostokątnej szachownicy znajduje się wąż. Chce on wykonać
dokładnie 3 przejścia przez szachownicę.
1. przejście - z lewego górnego rogu do prawego dolnego, poruszając się tylko
w prawo i w dół.
2. przejście - z prawego dolnego rogu do lewego górnego, poruszając się tylko
w górę i w lewo.
3. przejście - z lewego górnego rogu do prawego dolnego, poruszając się tylko
w prawo i w dół.
Wąż nigdy nie porusza się po skosie, tak wiec nie może w jednym kroku przejść
z pola (x,y) na (x+a,y+b) jeśli (a != 0 i b != 0).
Na każdym polu na planszy został zakopany skarb o pewnej wartości.
Ponieważ wąż jest bardzo zachłanny, dlatego pragnie wykonać swoje trzy przejścia
tak, aby suma skarbów które zbierze była maksymalna. Oczywiscie, jeśli już raz
zabierze skarb z jakiegoś pola, to ten skarb znika, i ponowne przechodzenie przez to pole nie zwiększa końcowej sumy.
Pomoż wężowi zaplanować najlepszą trasę!
W pierwszym wierszu wejścia znajdują się liczby całkowite n i m (1 <= n , m <= 50), oddzielone pojedynczym odstępem - liczba wierszy i kolumn planszy. W kolejnych n wierszach znajduje sie po m znakow ( '0' - '9' ) oznaczających wartości poszczególnych pól.
W pierwszej i jedynej linii wyjścia wypisz jedną liczbę całkowitą - maksymalny zysk jaki może osiągnąć wąż.
Dla danych wejściowych:
10 10 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789 0123456789
poprawnym wynikiem jest:
303
[Zgłoś rozwiązanie] [Moje zgłoszenia]