Candy Wall Burglary

The royal kitchen stores candy bars on one giant wall of shelves. There are $N$ shelves of equal length, stacked one above another from the floor up, with their left ends and their right ends lined up. Each shelf is divided into $M$ slots of equal size. A slot is either empty or holds one jar, and a jar holds between 1 and 9 candy bars.

Every shelf is joined to the shelf directly below it by one or more vertical ladders, and the bottommost shelf is joined to the floor the same way. A ladder joins a slot to the slot in the same column on the shelf below, or to the floor for the bottommost shelf. At most one ladder hangs directly under a given slot.

The topmost shelf holds no jars, and right above it an open window leads to the roof. A bandit came in through that window and wants to carry off as many candy bars as he can. His round trip runs like this:

• he starts on the topmost shelf;
• he goes down 0 or more shelves, possibly all the way to the floor;
• then he climbs back up and leaves through the window.

Once he starts climbing back up he never goes down again. On a shelf he walks left or right into a neighboring slot, and between two shelves he uses a ladder. Entering a slot that holds a jar takes every candy bar in that jar.

The alarm is his problem. The bandit must never enter a slot that holds a jar twice, because the second entry sets off the candy alarm. Empty slots, the topmost shelf and the floor may be crossed any number of times.

Compute the largest number of candy bars the bandit can carry off without setting off the alarm.

The first line has two integers $N$ and $M$, the number of shelves and the number of slots on one shelf.

The next $2N$ lines are strings of length $M$ that draw the shelves and the ladders from the top down.

• Line $2k - 1$ of the drawing, for $1 \le k \le N$, is the $k$-th shelf from the top. The character - is an empty slot, and a digit $x$ is a jar holding $x$ candy bars.
• Line $2k$ of the drawing is the row of ladders directly under the $k$-th shelf from the top. The character | is a ladder, and . is bare wall.

Constraints:

• $1 \le N \le 1000$
• $1 \le M \le 5000$
• The number of ladders directly under one shelf is at least 1 and at most 10.

Print one integer: the largest number of candy bars the bandit can collect without setting off the alarm.

• A slot at either end of a ladder may hold a jar.
• A slot is entered either by walking into it along a shelf or by reaching it as the end of a ladder. Using a ladder means entering both of its end slots.
• The topmost shelf and the floor hold no jars.
• The window spans the whole topmost shelf, so the bandit enters at any slot of that shelf and leaves from any slot of it.
• The floor is one continuous strip under the bottommost shelf, and the bandit walks along it freely.