JOI 군이 사는 IOI 시는 남북으로 \(H\)칸, 동서로 \(W\)칸인 직사각형이고 \(H \times W\)개의 구역으로 나뉘어 있다. 북에서 \(i\)번째, 서에서 \(j\)번째 구역을 \((i, j)\)라 한다. 지금 IOI 시에서 열리는 국제 프로그래밍 대회를 기념해 큰 축제가 열리고 있다. 몇몇 구역에는 포장마차가 나와 있고, 가게마다 다른 종류의 과자를 판다. 구역 \((1, 1)\), 구역 \((H, W)\)와 그 동서남북으로 이웃한 구역에는 포장마차가 없다. JOI 군은 구역 \((1, 1)\)에서 구역 \((H, W)\)로 간다. 이동 시간을 줄이려고 동쪽 또는 남쪽으로만 움직인다. 과자를 좋아하므로, 구역에 들어올 때마다 다음을 차례로 한다.
JOI 군은 같은 종류의 과자를 두 번 사지 않는다. IOI 시의 크기, 포장마차 위치와 각 가게 과자 값이 주어질 때, JOI 군이 구역 \((1, 1)\)에서 구역 \((H, W)\)로 가는 동안 사는 과자 값의 합의 최솟값을 구하라. |
입력은 다음 형식으로 주어진다.
\(H\) \(W\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_H\)
- 입력은 \(1+H\)줄이다.
- 첫째 줄에 정수 \(H\), \(W\)가 공백 하나로 구분되어 주어진다. IOI 시가 \(H \times W\)개의 구역으로 나뉘어 있음을 나타낸다.
- 이어지는 \(H\)줄에 각각 길이 \(W\)의 문자열이 공백 없이 주어지고, 각 구역 정보를 나타낸다. \(i\)번째 줄의 왼쪽에서 \(j\)번째 문자(\(1 \le i \le H\), \(1 \le j \le W\))는 구역 \((i, j)\)에 포장마차가 없으면 . 이다. 포장마차가 있으면 \(1, 2, \ldots, 9\) 가운데 하나이고 그 가게에서 파는 과자 값을 나타낸다.
- \(3 \le H \le 1000\)
- \(3 \le W \le 1000\)
- 채점 입력 \(1\)에서는 포장마차가 있는 구역 수가 \(20\) 이하이다.
다음 형식으로 출력한다.
첫째 줄에, JOI 군이 구역 \((1, 1)\)에서 구역 \((H, W)\)로 가는 동안 사는 과자 값의 합의 최솟값을 출력한다.
구역을 \((1, 1)\), \((2, 1)\), \((3, 1)\), \((3, 2)\), \((4, 2)\), \((4, 3)\), \((4, 4)\), \((4, 5)\), \((5, 5)\) 순으로 지나며, 구역 \((3, 1)\), \((3, 3)\), \((4, 2)\)의 포장마차에서 과자를 사면 합이 최소가 된다.