Гарри Поттер и тайная комната
Гарри Поттер ищет тайную комнату в замке Хогвардс. Замок имеет квадратную форму. В каждой комнате замка живет разное количество добрых или злых эльфов.
У Гарри есть карта замка (см. пример карты на рисунке). На карте отмечено количество эльфов в каждой комнате. Если эльфы добрые, то соответствующее число положительно, злые – отрицательно.
Гарри Поттер спросил профессора Дамблдора, как найти тайную комнату. Вот что ответил профессор:
— Пройди каждую строку комнат. Применяй два правила:
1. Если в строке комнат живут только добрые эльфы, то найди ту комнату, в которой живет наименьшее количество добрых эльфов. Иначе в строке комнат найди комнату, в которой живет наибольшее количество злых эльфов.
2. После того, как применил правило 1, смотри все комнаты в том же столбце, что и у найденной комнаты. Если в них живут только злые эльфы, то проверь, живет ли в найденной комнате наименьшее количество злых эльфов. Иначе проверь, живет ли в найденной комнате наибольшее количество добрых эльфов. Если проверка успешна, то это и есть тайная комната. Будь внимателен, так как в замке тайной комнаты может не быть вовсе.
— Ну и ну! Неужели нельзя найти тайную комнату как-то проще?! – подумал Гарри.
На рисунке изображена карта замка, имеющего размер 4´4 комнаты. В этом замке есть тайная комната – комната (4,3), в которой живет 5 добрых эльфов.
Напишите программу, которая по заданной карте замка поможет Гарри Поттеру найти тайную комнату и узнать количество эльфов, живущих в ней.
Входные данные
Целое число из диапазона 2..20 – количество комнат в строке на карте замка. Затем соответствующее количество строк с целыми числами из диапазона -500..500 – карта замка.
Выходные данные
Количество эльфов в тайной комнате или 0 (ноль), если тайной комнаты нет.
Примеры входных и выходных данных
INPUT. TXT | OUTPUT. TXT |
4 -6 –9 -10 1 -7 –21 -13 12 8 14 5 20 | 5 |
2 -10 1 -4 –2 | 4 |
