노점

문제

JOI 군이 사는 IOI 시는 남북 방향으로 H 구획, 동서 방향으로 W 구획인 직사각형 모양이며, H × W 개의 구획으로 나뉘어 있다. 북쪽에서 i 번째, 서쪽에서 j 번째 구획을 (i, j) 로 나타낸다. 현재 IOI 시에서 열리고 있는 국제 프로그래밍 대회를 기념하여 대규모 축제가 열리고 있다. 몇몇 구획에는 노점이 나와 있으며, 각각 다른 종류의 과자를 판매하고 있다. 구획 (1, 1), 구획 (H, W) 및 그 구획들과 동서남북으로 인접한 구획에는 노점이 없다.

JOI 군은 구획 (1, 1) 에서 구획 (H, W) 로 이동한다. 이동 시간을 줄이기 위해 JOI 군은 동쪽 또는 남쪽으로만 이동한다. JOI 군은 과자를 좋아하므로, 구획에 들어갈 때마다 다음 행동을 순서대로 한다.

1. 현재 구획에 아직 사지 않은 과자를 판매하는 노점이 나와 있는 경우, 그 노점에서 과자를 산다.
2. 현재 구획과 동서남북으로 인접한 구획에 아직 사지 않은 과자를 판매하는 노점이 나와 있는 경우, 그 노점들 중 하나를 제외한 모든 노점에서 판매원을 불러 과자를 산다.

JOI 군이 같은 종류의 과자를 여러 번 사는 일은 없다.

IOI 시의 크기, 노점의 위치와 각 노점의 과자 가격이 주어졌을 때, JOI 군이 구획 (1, 1) 에서 구획 (H, W) 로 이동하는 동안 사는 과자의 총액의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 1 + H 줄로 이루어진다.

1 번째 줄에는 두 정수 H, W (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000) 가 공백으로 구분되어 쓰여 있다. 이는 IOI 시가 H × W 개의 구획으로 나뉘어 있음을 나타낸다.

이어지는 H 줄에는 각각 W 개의 문자로 이루어진 문자열이 쓰여 있으며, IOI 시의 각 구획의 정보를 나타낸다. H 줄 중 i 번째 줄의 왼쪽에서 j 번째 문자 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는 구획 (i, j) 에 노점이 없는 경우에는 '.' (마침표) 이다. 노점이 있는 경우에는 '1', '2', ..., '9' 중 하나이며, 그 노점에서 판매하는 과자의 가격을 나타낸다.

주어지는 5 개의 입력 데이터 중 입력 1 에서는 노점이 있는 구획의 수가 20 이하이다.

출력

JOI 군이 구획 (1, 1) 에서 구획 (H, W) 로 이동하는 동안 사는 과자의 총액의 최솟값을 한 줄로 출력한다.

예제 입력 1

5 5
..483
.59.9
3.866
79...
4.8..

예제 출력 1

20

예제 1 에서는 구획 (1, 1), 구획 (2, 1), 구획 (3, 1), 구획 (3, 2), 구획 (4, 2), 구획 (4, 3), 구획 (4, 4), 구획 (4, 5), 구획 (5, 5) 의 순서로 이동하여 구획 (3, 1), 구획 (3, 3), 구획 (4, 2) 의 노점에서 판매하는 과자를 사면 사는 과자의 총액이 최소가 된다.

예제 입력 2

12 10
..498522.4
.633527629
54.4621596
634.213458
1924518685
7739539767
276155.3.6
87716372.2
.858877595
7998739511
3438.5852.
568.9319..

예제 출력 2

63