Problem G
Using Digits
He must begin by stepping onto the square closest to himself, which we can think of as square $(1, 1)$, and walk to some other square, which we can think of as square $(X, Y)$ for some $X, Y > 1$. Each step he takes is in either the positive-X or positive-Y direction, one square at a time. Every square has a number on it in the range $0$ to $9$, and the grid carefully monitors which squares he steps on. When he reaches the door, if the sum of the squares that he stepped on is sufficiently small, the door will open and he will be free. If not, he will be trapped forever.
After scanning the board for a while Agent Youdy becomes convinced that there is no path to success. But then he remembers a cryptic Code Key that he found while searching the lair. He reaches into his pocket and removes a paper with a large integer on it, each of whose digits is in the range $1$ to $9$. His training kicks in again, and he remembers the way this works: whenever he wishes, he may use the leading digit of the key, which permits him to hop over exactly that many squares. Whenever he uses a leading digit, it is removed from the number. Note that hops, no matter how far, change only his $x$- or $y$-coordinate, but not both.
For example, starting at the “1” on the bottom left corner in the figure shown, with Code Key $11$, his best path is step right, step right, hop right, hop up, step right, step up, for a total of $1+0+3+2+1+1+8=16$. But starting with Code Key $12$, his best path is step right, hop up, hop right, step right, step up, for a total of $18$.
![\includegraphics[width=0.3\textwidth ]{sample.png}](/problems/usingdigits/file/statement/en/img-0002.png)
Input
The first line of input contains two space-separated integers $X$ and $Y$, giving the width and height of the grid ($1\leq X, Y \leq 100$). The next line contains a positive integer, the Code Key, guaranteed to be less than $10^{50}$ and containing only positive digits. Then follow $Y$ lines, each containing $X$ digits, giving the numbers on the grid of squares. The last digit of the first of these lines represents Agent Youdy’s destination, and the first digit of the last line represents his starting square.
Output
The smallest sum possible on a path from $(1, 1)$ to $(X, Y)$, including the endpoints.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 4 11 329178 978211 837698 103725 |
16 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 4 12 329178 978211 837698 103725 |
18 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 4 23232345 329178 978211 837698 103725 |
11 |
