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