A Walk Through Brooklyn

Miles Morales walks through Brooklyn. Seen from a bird's eye view, Brooklyn looks like a grid field of $n \times m$ cells, whose vertical sides are parallel to the north-south direction. Each cell belongs to a house. Houses are regions of cells connected by sides. Every unit segment on the boundary of the field or between two different houses is a road. Miles starts his walk on the northern boundary of Brooklyn. He moves along the roads to the west, east, or south. He never walks along the same road twice, even in opposite directions. He keeps walking until he reaches the southern boundary of Brooklyn. Miles's route divides Brooklyn into two parts: the part east of the route and the part west of it. Miles wants to know the minimum possible difference between the areas of these two parts. Help him answer this question.

The first line contains two integers $n$ and $m$, the size of the field ($1 \le n, m \le 300$).

The next $n$ lines each contain $m$ uppercase Latin letters that describe Brooklyn. Side-connected cells with the same letter form one house.

Print one integer, the minimum possible difference between the areas of the two parts that Miles's route divides Brooklyn into.

The picture for the first test. Houses are shapes of different colors, and roads are the black segments. A possible route of Miles is drawn as a red dashed line.

The picture for the second test.