브루클린 산책

마일스 모랄레스가 브루클린을 걷고 있다. 하늘에서 내려다보면 브루클린은 세로 변이 남북 방향과 평행한 $n \times m$ 격자 들판처럼 보인다. 들판의 각 칸은 어느 한 집에 속한다. 집은 변을 공유하며 연결된 칸들의 영역이다. 들판의 경계 위에 있거나 서로 다른 두 집 사이에 있는 모든 단위 선분은 도로이다. 마일스는 브루클린 북쪽 경계에서 산책을 시작한다. 그는 서쪽, 동쪽, 또는 남쪽 도로를 따라 움직인다. 방향이 반대여도 같은 도로를 두 번 지나지 않는다. 브루클린 남쪽 경계에 도착할 때까지 계속 걷는다. 마일스의 경로는 브루클린을 경로 동쪽 부분과 서쪽 부분으로 나눈다. 마일스는 두 부분 넓이 차이의 최솟값이 궁금하다. 이 질문에 답을 구하라.

첫 줄에 들판의 크기를 나타내는 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 300$).

다음 $n$개 줄에는 각각 $m$개의 대문자 라틴 문자가 주어지며, 브루클린을 나타낸다. 변을 공유하며 연결된 같은 글자의 칸들이 하나의 집이다.

마일스의 경로가 브루클린을 나누는 두 부분 넓이 차이의 최솟값을 한 줄에 정수로 출력한다.

첫 번째 테스트의 그림이다. 집은 색이 다른 도형이고, 도로는 검은 선분이다. 마일스가 가능한 경로는 빨간 점선으로 그려져 있다.

두 번째 테스트의 그림이다.