eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Король севера

Король севера

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Зима пришла (или уже идет? кто знает эти дни) и новый король поднимается на Севере. Информация поступает быстро в эти дни... Именно поэтому у Вас, молодого короля, не так много осталось времени. Вам необходимо собрать армию знаменосцев. Но на один вопрос кажется сложнее ответить, нежели Вы это предполагали. Насколько велико королевство на которое Вы можете претендовать и сколько мужчин следует отправить на его защиту? Ваши консультанты внимательно изучили потенциальное государство и определили, сколько потребуется Ваших знаменосцев чтобы в полной мере защитить любую часть карты против Ваших врагов. Вы как любящий и заботливый король хотите свести к минимуму количество людей, которые должны служить у Вас в армии. Для того чтобы Ваш военный совет принял правильное решение как лучше защитить королевство, Вы должны определить размер необходимой Вам армии.

К счастью, вражеские армии не такие уж и передовые. Вам достаточно защитить себя только от армий, движущихся по горизонтали или по вертикали (армия не может пройти мимо Ваших знаменосцев по диагонали). Ваше королевство считается защищенным, если нельзя добраться до Вашего замка, стартовав где-нибудь за пределами карты и при этом не пересекая защищенные области. Квадраты, обозначенные 0 на карте, являются высокими горами или стенами, никто их не может пересечь. Вам не следует защищать их знаменосцами. Так как Вы не владеете информацией о том, что скрывается за стеной (или в нашем случае за границами карты), то Вам следует готовиться к худшему. В планах Вам не следует занимать клетки за пределами карты.

prb6037

Рисунок - Иллюстрация к примеру - королевство защищено минимальной армией из 37 знаменосцев, расположенных в позиция, указанных крестиком. Королевство изображено в виде сетки. Вам не следует узнать что-то новое о королевстве или найти место расположения знаменосцев. Эти вопросы должен решать Ваш военный совет.

Входные данные

Задается в форме прямоугольной стратегической карты, которую принесли Ваши советники. Каждый квадрат карты обозначен количеством знаменосцев, необходимых для его защиты против предполагаемой армии. Формат карты следующий: первая строка содержит целые числа R и C (3R, C300) - размеры карты. Далее следует R строк, каждая из которых содержит C целых чисел c[i] (0c[i]100000) - количество знаменосцев, необходимых для защиты каждого квадрата. В конце задаются r (0 < r < R - 1) и c (0 < c < C - 1) - положение Вашего замка на карте.

Выходные данные

Вывести наименьший возможный размер Вашей армии для защиты королевства.

Пример

Входные данные #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
Выходные данные #1
37
Источник German Collegiate Programming Contest 2013, Problem H