쇼핑

격자 모양의 도시가 있다. 도시는 $H$행 $W$열이고, 각 칸에는 가게가 하나 있거나 아무것도 없다. 가게마다 파는 물건이 서로 다르며, 물건 하나의 가격은 1 이상 9 이하의 정수다.

당신은 칸 $(1, 1)$에서 출발해 칸 $(H, W)$까지 걸어간다. 이동은 오른쪽 칸이나 아래 칸으로만 할 수 있다.

출발 칸을 포함해 어떤 칸에 도착할 때마다 다음 순서로 쇼핑한다.

1. 도착한 칸에 아직 물건을 사지 않은 가게가 있으면 그 물건을 산다.
2. 도착한 칸과 상하좌우로 인접한 칸 가운데, 아직 물건을 사지 않은 가게가 있는 칸을 모두 모은다. 그런 칸이 하나라도 있으면 그중 정확히 한 칸을 골라 건너뛰고 나머지 칸의 물건을 모두 산다. 그런 칸이 없으면 아무것도 사지 않는다.

한 가게에서는 물건을 한 번만 산다. 2번에서 어느 칸을 건너뛸지는 매번 자유롭게 고른다. 한 번 건너뛴 가게라도 나중에 그 옆 칸에 다시 도착하면 그때 사게 된다.

경로와 건너뛸 칸을 모두 최선으로 골랐을 때 쓰는 금액의 최솟값을 구하시오.

첫째 줄에 도시의 행 수와 열 수를 나타내는 정수 $H$와 $W$가 공백으로 구분되어 주어진다. ($3 \le H \le 1000$, $3 \le W \le 1000$)

둘째 줄부터 $H$개의 줄에 길이가 $W$인 문자열이 한 줄에 하나씩 주어진다. $i$번째 줄의 $j$번째 문자는 칸 $(i, j)$의 상태를 나타낸다. 문자가 "."이면 그 칸에는 가게가 없고, "1"부터 "9"까지의 숫자면 그 칸에 가게가 있으며 그 숫자가 물건의 가격이다.

첫째 줄에 쓰는 금액의 최솟값을 출력한다.