Problem description


Kratka kontratakuje
(kratka-2)
Memory limit: 128 MB
Time limit: 5.00 s

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
4 3
10 8 0
5 0 2
0 9 1
1 2 9
34