{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:35.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e1f1e3ac1cf7f8353cba53e22a102c9d?v\u003d1714817360\" alt\u003d\"/problems/usingdigits/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003eAs the door slams shut behind Agent Youdy, he realizes\n that his daring escape from his arch-enemy’s lair is not quite\n done. Before him lies a grid of numbered squares, and off in\n the distance he sees the exit door. He recognizes this setup\n from his training. It’s a Sum Trap, and works as follows:\n \u003cp\u003eHe must begin by stepping onto the square closest to\n himself, which we can think of as square \u003cspan class\u003d\"tex2jax_process\"\u003e$(1, 1)$\u003c/span\u003e, and walk to some other\n square, which we can think of as square \u003cspan class\u003d\"tex2jax_process\"\u003e$(X, Y)$\u003c/span\u003e for some \u003cspan class\u003d\"tex2jax_process\"\u003e$X, Y \u0026gt; 1$\u003c/span\u003e. Each step he takes is\n in either the positive-X or positive-Y direction, one square at\n a time. Every square has a number on it in the range\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e, and the grid carefully monitors\n which squares he steps on. When he reaches the door, if the sum\n of the squares that he stepped on is sufficiently small, the\n door will open and he will be free. If not, he will be trapped\n forever.\u003c/p\u003e\n \u003cp\u003eAfter scanning the board for a while Agent Youdy becomes\n convinced that there is no path to success. But then he\n remembers a cryptic Code Key that he found while searching the\n lair. He reaches into his pocket and removes a paper with a\n large integer on it, each of whose digits is in the range\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e. His training kicks in again, and\n he remembers the way this works: whenever he wishes, he may use\n the leading digit of the key, which permits him to hop over\n exactly that many squares. Whenever he uses a leading digit, it\n is removed from the number. Note that hops, no matter how far,\n change only his \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e- or\n \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e-coordinate, but not\n both.\u003c/p\u003e\n \u003cp\u003eFor example, starting at the “1” on the bottom left corner\n in the figure shown, with Code Key \u003cspan class\u003d\"tex2jax_process\"\u003e$11$\u003c/span\u003e, his best path is step right,\n step right, hop right, hop up, step right, step up, for a total\n of \u003cspan class\u003d\"tex2jax_process\"\u003e$1+0+3+2+1+1+8\u003d16$\u003c/span\u003e. But\n starting with Code Key \u003cspan class\u003d\"tex2jax_process\"\u003e$12$\u003c/span\u003e, his best path is step right, hop\n up, hop right, step right, step up, for a total of \u003cspan class\u003d\"tex2jax_process\"\u003e$18$\u003c/span\u003e.\u003c/p\u003e\n \u003cdiv id\u003d\"fig\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/18c8168d546e78f309088f7ee3d20456?v\u003d1714817360\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{sample.png}\" style\u003d\"width:30.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration for the sample inputs.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains two space-separated\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$X$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$Y$\u003c/span\u003e, giving the width and\n height of the grid (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq X, Y\n \\leq 100$\u003c/span\u003e). The next line contains a positive integer,\n the Code Key, guaranteed to be less than \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{50}$\u003c/span\u003e and containing only positive\n digits. Then follow \u003cspan class\u003d\"tex2jax_process\"\u003e$Y$\u003c/span\u003e\n lines, each containing \u003cspan class\u003d\"tex2jax_process\"\u003e$X$\u003c/span\u003e\n digits, giving the numbers on the grid of squares. The last\n digit of the first of these lines represents Agent Youdy’s\n destination, and the first digit of the last line represents\n his starting square.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eThe smallest sum possible on a path from \u003cspan class\u003d\"tex2jax_process\"\u003e$(1, 1)$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$(X, Y)$\u003c/span\u003e, including the endpoints.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 4\n11\n329178\n978211\n837698\n103725\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 4\n12\n329178\n978211\n837698\n103725\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 4\n23232345\n329178\n978211\n837698\n103725\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}