Problem description
Kojarzysz takie zadanie Kratka? Tak? No to powodzenia tym razem! Nie? Jakże mi przykro… Na szczęście możesz od razu zacząć od trudniejszego zadania.
Dana jest prostokąt wymiaru N × M wypełniony liczbami. Należy wybrać liczby o jak największej sumie, nie wolno jednak wybrać dwóch leżących w sąsiednich komórkach prostokąta. Dwie komórki prostokąta uznajemy za sąsiednie jeśli dzielą bok.
Napisz program, który: wczyta wymiary prostokąta oraz umieszczone w nim liczby, wyznaczy maksymalną możliwą sumę liczb, które można wybrać zgodnie z zasadami i wypisze wynik na wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, określające wysokość i szerokość prostokąta. W kolejnych N wierszach znajduje się po M liczb Ai, j. Są to liczby umieszczone w prostokącie.
Wyjście
W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć maksymalna suma liczb, które można wybrać zgodnie z regułami podanymi powyżej.
Ograniczenia
1 ≤ N, M ≤ 50, 0 ≤ Ai, j ≤ 1 000 000.
Przykład
| Input | Output | |
|
|