28838번 - Прогулка по Бруклину 다국어

Майлз Моралес гуляет по Бруклину. С высоты птичьего полета, Бруклин выглядит как клетчатое поле $n \times m$, вертикальные стороны которого параллельны направлению север-юг. Каждая клетка этого поля принадлежит какому-либо дому. Дома образуют связные по стороне области клеток. Все единичные отрезки, находящиеся на границе поля или между двумя разными домами, являются дорогами. Майлз начинает свою прогулку на северной границе Бруклина. Майлз будет идти по дорогам на запад, восток или юг. При этом, он никогда не будет проходить по одной дороге дважды, даже в различных направлениях. Майлз будет гулять до тех пор, пока не дойдет до южной границы Бруклина. Маршрут Майлза разделит Бруклин на две части: ту, которая находится восточнее маршрута Майлза, и ту, которая находится западнее. Майлза интересует, какова минимальная возможная разница площадей этих частей. Помогите Майлзу ответить на этот вопрос.

В первой строке даны два целых числа $n$ и $m$ --- размеры поля ($1 \le n, m \le 300$).

В следующих $n$ строках дано по $m$ заглавных латинских букв --- описание Бруклина. Связные по стороне области клеток, состоящие из одинаковых букв, являются домами.

В единственной строке выведите одно целое число --- минимальную возможную разницу площадей двух частей, на которые маршрут Майлза разделит Бруклин.

Иллюстрация к первому тесту. Дома --- фигуры разного цвета, дороги --- черные отрезки. Возможный маршрут Майлза нарисован красной пунктирной линией.

Иллюстрация ко второму тесту.