{"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 \u003cp\u003eWinter is coming (or going? who can be sure these days) and\n a new king rises in the North. The message travels quickly\n these days... That is why you, the rising king, have not much\n time left. You need to rally your bannermen behind you. But one\n question seems harder to answer than you would have first\n expected. How large of a kingdom can you claim and how many men\n should you send for? Your advisors have taken a close look at\n the potential kingdom and have determined how many of your\n bannermen would be required to fully defend any part of the map\n against your foes. As you are a loving and caring king, you\n want to minimize the number of men that have to serve in your\n army. To give your war council a fair chance of figuring out\n the best kingdom to defend, you have to determine the size of\n the army that you will raise as soon as possible.\u003c/p\u003e\n \u003cp\u003eLuckily, armies are not that advanced yet. You will only\n have to defend against armies moving horizontally or vertically\n (an army cannot pass by your bannermen diagonally). Your\n kingdom counts as defended, if there is not a single way to\n reach your castle, starting anywhere outside of the map,\n without passing to a fully defended area. Squares on the map\n labeled \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e represent high\n mountains, or walls, no one would ever be foolish enough to\n climb. You can assume to be safe from invasion without sending\n any bannermen to defend them. Since you are uncertain about\n what lurks behind the wall (or in our case the borders of the\n map), you have to assume the worst and plan as if you would\n never be able to hold any position outside of the given\n map.\u003c/p\u003e\n \u003cdiv id\u003d\"a0000000004\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/682e3c722c47cf14aad3059a7ebb2ec0?v\u003d1715134281\" alt\u003d\"\\includegraphics[width\u003d0.4\\textwidth ]{img/defend.pdf}\" style\u003d\"width:40.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of the sample input — the\n kingdom can be defended with a minimal army of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$37$\u003c/span\u003e bannermen,\n located at the cross-marked positions. The kingdom itself\n is illustrated using a tiling pattern. Note that you do\n not have to find out about the kingdom, or the position\n of your bannermen. These questions are to be figured out\n by your war council.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input is given in the form of the (rectangular)\n strategic map which your advisors came up with. Every square in\n the map is assigned a number of bannermen which would be\n required to defend the position against any potential army. The\n map is formatted as follows: In the first line you are given\n two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$R$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$C$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$3 \\leq R,C \\leq 300$\u003c/span\u003e, specifying the\n dimensions of the map. This line is followed by \u003cspan class\u003d\"tex2jax_process\"\u003e$R$\u003c/span\u003e lines, each containing\n \u003cspan class\u003d\"tex2jax_process\"\u003e$C$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq c_ i \\leq 100\\, 000$\u003c/span\u003e, the\n number of bannermen necessary to defend each square. Finally,\n you are given \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; r \u0026lt;\n R-1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; c \u0026lt;\n C-1$\u003c/span\u003e, the position of your own castle on the map.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput an integer on a single line, the smallest possible\n army you would require to defend the kingdom given in the\n input.\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\u003e7 8\n42 42 0 0 0 0 0 16\n42 11 14 42 42 42 10 16\n42 0 42 42 42 42 0 16\n42 0 42 42 42 42 0 42\n42 0 42 42 42 42 0 42\n42 11 42 42 42 5 5 42\n42 42 0 0 0 42 42 42\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e37\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}