У Поликарпа есть клетчатый лист бумаги размера n × m. Поликарп закрасил некоторые клетки этого листа чёрным цветом, остальные остались белыми. Вдохновленный историей о картине Малевича «Черный квадрат», Поликарп решил закрасить минимальное количество белых клеток листа в чёрный цвет так, чтобы все чёрные клетки на листе бумаги образовывали квадрат.
Перед вами стоит задача определить минимальное количество клеток, которые нужно закрасить в чёрный цвет, чтобы получился чёрный квадрат со сторонами параллельными сторонам листа? Все клетки, не принадлежащие квадрату, должны быть белого цвета. Сторона квадрата должна иметь ненулевую длину.
Выходные данные
Выведите минимальное количество клеток, которые нужно закрасить в чёрный цвет, чтобы получился чёрный квадрат со сторонами параллельными сторонам листа. Все клетки, не принадлежащие квадрату, должны быть белого цвета. Если этого сделать невозможно, выведите -1.
Примечание
В первом примере нужно закрасить 5 клеток — (2, 2), (2, 3), (3, 2), (3, 3) и (4, 2). Тогда получится квадрат с длиной стороны равной трём, а левый верхний угол квадрата будет находиться в точке (2, 2).
Во втором примере все клетки поля изначально закрашены в чёрный цвет и образуют прямоугольник, поэтому квадрат получить невозможно.
В третьем примере все клетки поля изначальное закрашены в белый цвет, поэтому достаточно закрасить любую из клеток поля, чтобы получить квадрат с длиной стороны равной единице.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
WWWW
WWWB
WWWB
WWBB
WWWW
|
5
|
|
2
|
1 2
BB
|
-1
|
|
3
|
3 3
WWW
WWW
WWW
|
1
|