사탕 벽 털기

문제

왕실 주방에는 사탕 바를 보관하는 거대한 선반 벽이 있다. 길이가 같은 선반 $N$ 개가 바닥에서부터 위로 차곡차곡 놓여 있고, 왼쪽 끝과 오른쪽 끝이 모두 가지런히 맞춰져 있다. 선반 하나는 크기가 같은 칸 $M$ 개로 나뉜다. 각 칸은 비어 있거나 항아리 하나가 놓여 있고, 항아리 하나에는 사탕 바가 1개 이상 9개 이하로 들어 있다.

모든 선반은 바로 아래 선반과 수직 사다리 한 개 이상으로 이어져 있고, 맨 아래 선반은 같은 방식으로 바닥과 이어져 있다. 사다리는 어떤 칸과 바로 아래 선반의 같은 열에 있는 칸을 잇는다. 맨 아래 선반에 걸린 사다리는 바닥으로 이어진다. 한 칸 바로 아래에 걸린 사다리는 많아야 한 개다.

맨 위 선반에는 항아리가 없고, 그 바로 위에는 옥상으로 통하는 창문이 열려 있다. 도둑은 이 창문으로 들어와 사탕 바를 최대한 많이 들고 나가려 한다. 도둑의 왕복 경로는 이렇다.

맨 위 선반에서 출발한다.
선반을 0개 이상 내려간다. 바닥까지 내려갈 수도 있다.
그런 다음 다시 올라와 창문으로 나간다.

한 번 올라가기 시작하면 다시 내려가지 않는다. 선반 위에서는 이웃한 칸으로 왼쪽이나 오른쪽으로 걸어가고, 선반과 선반 사이는 사다리로 오르내린다. 항아리가 있는 칸에 들어가면 그 항아리에 든 사탕 바를 모두 가져간다.

문제는 경보다. 항아리가 있는 칸에는 두 번 들어갈 수 없고, 두 번째로 들어가는 순간 사탕 경보가 울린다. 빈 칸과 맨 위 선반, 바닥은 몇 번이든 지나가도 된다.

경보를 울리지 않고 도둑이 들고 나갈 수 있는 사탕 바의 최대 개수를 구하시오.

입력

첫째 줄에 선반의 수 $N$ 과 선반 하나의 칸 수 $M$ 이 주어진다.

다음 $2N$ 개 줄은 각각 길이가 $M$ 인 문자열이고, 선반과 사다리 배치를 위에서부터 차례로 그린다.

그림의 $2k - 1$ 번째 줄( $1 \le k \le N$ )은 위에서 $k$ 번째 선반이다. 문자 -는 빈 칸이고, 숫자 $x$ 는 사탕 바 $x$ 개가 든 항아리다.
그림의 $2k$ 번째 줄은 위에서 $k$ 번째 선반 바로 아래에 걸린 사다리다. 문자 |는 사다리이고, .는 빈 벽이다.

제한:

$1 \le N \le 1000$
$1 \le M \le 5000$
선반 하나 바로 아래에 걸린 사다리는 1개 이상 10개 이하다.

출력

경보를 울리지 않고 도둑이 모을 수 있는 사탕 바의 최대 개수를 한 줄에 출력한다.

힌트

사다리의 양 끝이 닿는 칸에도 항아리가 있을 수 있다.
칸에 들어가는 방법은 선반 위를 걸어 들어가는 것과 사다리 끝에 닿는 것이다. 사다리를 이용하면 그 양 끝 칸에 반드시 들어간다.
맨 위 선반과 바닥에는 항아리가 없다.
창문은 맨 위 선반 전체에 걸쳐 열려 있어서, 도둑은 맨 위 선반의 어느 칸으로든 들어오고 어느 칸으로든 나간다.
바닥은 맨 아래 선반 아래로 끊김 없이 이어진 하나의 통로이고, 도둑은 그 위를 자유롭게 걸어 다닌다.