Using Digits

요원 Youdy의 등 뒤에서 문이 쾅 닫히고, 그는 숙적의 소굴에서의 대담한 탈출이 아직 끝나지 않았음을 깨닫는다. 그의 앞에는 숫자가 적힌 격자가 펼쳐져 있고, 멀리 출구 문이 보인다. 그는 훈련에서 이 상황을 본 적이 있다. 이것은 합 함정이고, 다음과 같이 작동한다.

그는 먼저 자신에게 가장 가까운 칸, 즉 칸 $(1, 1)$ 에 발을 들여놓고, 다른 칸, 즉 $X, Y > 1$ 인 칸 $(X, Y)$ 까지 걸어가야 한다. 각 걸음은 양의 $X$ 방향 또는 양의 $Y$ 방향으로 한 번에 한 칸씩 움직인다. 모든 칸에는 0에서 9 사이의 숫자가 적혀 있고, 격자는 그가 밟은 칸을 주의 깊게 감시한다. 그가 문에 도달했을 때, 밟은 칸들의 합이 충분히 작으면 문이 열리고 그는 자유로워진다. 그렇지 않으면 그는 영원히 갇히게 된다.

잠시 동안 판을 살펴본 후 Youdy 요원은 성공으로 가는 길이 없다고 확신한다. 그러나 그때 그는 소굴을 수색하다 발견한 수수께끼 같은 코드 키를 떠올린다. 그는 주머니에 손을 넣어 큰 정수가 적힌 종이를 꺼낸다. 그 정수의 각 자릿수는 1에서 9 사이에 있다. 훈련이 다시 발동되고, 그는 그 작동 방식을 기억한다. 즉, 원할 때마다 키의 선두 자릿수를 사용할 수 있고, 그것으로 그 숫자만큼 칸을 뛰어넘을 수 있다. 선두 자릿수를 사용할 때마다 그것은 수에서 제거된다. 뛰어넘기는 아무리 멀어도 $x$ 좌표 또는 $y$ 좌표 중 하나만 바꾸고, 둘 다는 바꾸지 않는다.

예를 들어, 그림에 표시된 왼쪽 아래 모서리의 "1"에서 시작하여 코드 키 11인 경우, 그의 최선의 경로는 오른쪽으로 걷기, 오른쪽으로 걷기, 오른쪽으로 뛰기, 위로 뛰기, 오른쪽으로 걷기, 위로 걷기이며, 합계는 $1+0+3+2+1+1+8 = 16$ 이다. 그러나 코드 키 12로 시작하는 경우, 그의 최선의 경로는 오른쪽으로 걷기, 위로 뛰기, 오른쪽으로 뛰기, 오른쪽으로 걷기, 위로 걷기이며, 합계는 18이다.

그림 D.1: 예제 입력에 대한 설명.

입력의 첫 번째 줄에는 공백으로 구분된 두 정수 $X$ 와 $Y$ 가 포함되어 격자의 너비와 높이를 나타낸다 ($1 \le X, Y \le 100$). 다음 줄에는 양의 정수인 코드 키가 포함되어 있으며, $10^{50}$ 미만이고 양의 자릿수만 포함하는 것이 보장된다. 그런 다음 $Y$ 개의 줄이 이어지며, 각 줄은 $X$ 개의 자릿수를 포함하여 격자 칸의 숫자를 나타낸다. 이 줄들 중 첫 번째 줄의 마지막 자릿수는 Youdy 요원의 목적지를 나타내고, 마지막 줄의 첫 번째 자릿수는 그의 시작 칸을 나타낸다.

$(1, 1)$ 에서 $(X, Y)$ 로 가는 경로에서 가능한 최소 합계를 끝점을 포함하여 출력하라.