Есть клетчатый квадрат размера \(n \times n\). Некоторые клетки квадрата покрашены в черный цвет, остальные клетки покрашены в белый. За одну операцию разрешается выбрать некоторый прямоугольник и перекрасить все его клетки в белый цвет. За перекраску прямоугольника размера \(h \times w\) взимается штраф в размере \(\max(h, w)\). Требуется за минимальный суммарный штраф покрасить все клетки в белый цвет.
В первой строке через пробел задано одно целое число \(n\) — размер квадрата (\(1 \leq n \leq 50\)).
В следующих \(n\) строках записаны строки длины \(n\), состоящие из символов . и #. Если \(j\)-й символ \(i\)-й строки равен #, то клетка квадрата с координатами \((i, j)\) является чёрной, иначе — белой.
Выведите одно число — минимальный суммарный штраф покраски всего квадрата в белый цвет.
На картинке вы можете видеть четыре примера и некоторые из оптимальных способов их покрасить.
3 ### #.# ###
3
3 ... ... ...
0
4 #... .... .... #...
2
5 #...# .#.#. ..... .#... #....
5
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач