Problem D
The King of the North
Winter is coming (or going? who can be sure these days) and a new king rises in the North. The message travels quickly these days... That is why you, the rising king, have not much time left. You need to rally your bannermen behind you. But one question seems harder to answer than you would have first expected. How large of a kingdom can you claim and how many men should you send for? Your advisors have taken a close look at the potential kingdom and have determined how many of your bannermen would be required to fully defend any part of the map against your foes. As you are a loving and caring king, you want to minimize the number of men that have to serve in your army. To give your war council a fair chance of figuring out the best kingdom to defend, you have to determine the size of the army that you will raise as soon as possible.
Luckily, armies are not that advanced yet. You will only
have to defend against armies moving horizontally or vertically
(an army cannot pass by your bannermen diagonally). Your
kingdom counts as defended, if there is not a single way to
reach your castle, starting anywhere outside of the map,
without passing to a fully defended area. Squares on the map
labeled
![\includegraphics[width=0.4\textwidth ]{img/defend.pdf}](/problems/thekingofthenorth/file/statement/en/img-0001.png)
Input
The input is given in the form of the (rectangular)
strategic map which your advisors came up with. Every square in
the map is assigned a number of bannermen which would be
required to defend the position against any potential army. The
map is formatted as follows: In the first line you are given
two integers
Output
Output an integer on a single line, the smallest possible army you would require to defend the kingdom given in the input.
Sample Input 1 | Sample Output 1 |
---|---|
7 8 42 42 0 0 0 0 0 16 42 11 14 42 42 42 10 16 42 0 42 42 42 42 0 16 42 0 42 42 42 42 0 42 42 0 42 42 42 42 0 42 42 11 42 42 42 5 5 42 42 42 0 0 0 42 42 42 3 4 |
37 |