Retiring replicants P85975

It’s night and it’s raining. Rick Deckard is in the north-western house of a rectangular block of houses, crowded with replicants. Rick wants to “retire” (that is, kill) as many replicants as possible while going to the south-eastern house of the block. Rick can only move by jumping across the roofs of houses that are vertically or horizontally adjacent. When Rick enters a house, the ensuing fight to retire all replicants in the house causes so much destruction that he is just in time to leave the house before it collapses, so he cannot enter it anymore.

[rf]

Given a map with the number of replicants at each house, compute the number of replicants that Rick can “retire” while going from the north-western corner to the south-eastern corner, never repeating a house and always moving either horizontally or vertically.

[r]

Input

Input has several cases. Each case begins with the dimensions n × m of the map. Follow n rows with m positive integer numbers each. For every case, the sum of all its numbers is smaller than 10⁹.

Output

For every case, print the maximum number of replicants that Rick can “retire”.