시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 23 16 8 66.667%

문제

쇼핑을 매우 좋아하는 경곽이는 JOI시로 여행을 왔다. JOI시는 H행 W열로 구성된 격자 도시이다.

이 도시에 각 위치에는 가게가 있을 수 있다. 그리고 각 가게들은 모두 서로 다른 물건들을 판매한다.

경곽이는 (1, 1)에서 출발하여 (H, W)까지 이동할 예정이다. 가이드는 경곽이의 쇼핑 낭비를 최소화하기 위해서 JOI시에서 최단 경로로만 이동하려고 한다. 즉, 아래 또는 오른쪽으로만 이동할 예정이다.

경곽이는 각 위치에 도달하면 다음과 같이 쇼핑한다.

  1. 만약 경곽이가 이동한 위치에 아직 쇼핑을하지 않은 가게가 있다면 그 물건을 산다.
  2. 그 뿐만 아니라 현재 위치와 인접(상, 하, 좌, 우)한 위치에도 아직 쇼핑을 하지 않은 가게가 있다면 그 가게들 중 한 가게만 제외하고, 다른 모든 곳의 물건을 산다.

경곽이는 자신의 쇼핑 중독이 너무 심함을 알고 있기에 주변에 인접한 가게들에서는 적어도 한 가게에서는 쇼핑을 참는다 (ㅠㅠ) 따라서 인접한 곳 중에서는 한 곳만 제외한 나머지를 싹쓸이 한다.

이러한 경곽이가 최소한의 돈을 낭비할 수 있도록 JOI시의 (1, 1)에서 출발하여 (H, W)까지 안내하는 프로그램을 작성하는 것이 여러분의 목표이다.

경곽이가 쓰는 금액의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 도시의 행과 열을 나타내는 정수 H, W가 공백으로 구분되어 입력된다. (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000)

다음 줄부터 H줄에 걸쳐서 W개로 이루어진 문자열이 입력된다.

이 값들은 상점의 정보를 나타낸다.

만약 그 칸이 "."라면 가게가 없음을 의미한다.

만약 그 칸의 값이 "1" ~ "9"로 표시되어 있다면, 그 위치에는 상점이 있고 그 상점에서 물건을 살 때 드는 비용을 의미한다.

출력

목적지까지 경곽이가 최소한의 낭비를 하도록 이동했을 경우 경곽이가 사용한 금액을 출력한다.

예제 입력

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

예제 출력

20

예제 입력 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

힌트