O. Два государства: разрез по столбцам

Игровое поле — квадрат $n \times n$, в некоторых клетках стоят города; городов чётное число и не меньше двух.

Поле делят на два связных государства с равным числом городов. Разрез фиксирован: клетки обходят змейкой по столбцам — первый столбец сверху вниз, второй снизу вверх, третий снова сверху вниз и так далее. Первому государству достаётся начальный кусок обхода, второму — остальное.

Выведите наименьшее число клеток, которое может достаться первому государству.

Первая строка содержит число $n$ ($1 \le n \le 50$).

Следующие $n$ строк содержат по $n$ букв: C — клетка с городом, D — пустая клетка.

Одно число — количество клеток первого государства.