F2. Алиса и перекрашивание 2
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Разница между версиями заключается в стоимости операций. Решение для одной версии не будет работать для другой!

У Алисы есть таблица размером $$$n \times m$$$, изначально все ее клетки окрашены в белый цвет. Клетка на пересечении $$$i$$$-й строки и $$$j$$$-го столбца обозначается как $$$(i, j)$$$. Алиса может выполнять следующие операции:

  • Выбрать любой подпрямоугольник, содержащий клетку $$$(1, 1)$$$, и инвертировать цвета всех его клеток. (Инвертировать означает изменить цвет клетки с белого на черный или с черного на белый).

    Эта операция стоит $$$1$$$ монету.

  • Выбрать любой подпрямоугольник, содержащий клетку $$$(n, 1)$$$, и инвертировать цвета всех его клеток.

    Эта операция стоит $$$3$$$ монеты.

  • Выбрать любой подпрямоугольник, содержащий клетку $$$(1, m)$$$, и инвертировать цвета всех его клеток.

    Эта операция стоит $$$4$$$ монеты.

  • Выбрать любой подпрямоугольник, содержащий клетку $$$(n, m)$$$, и инвертировать цвета всех его клеток.

    Эта операция стоит $$$2$$$ монеты.

Напомним, что подпрямоугольник — это все клетки $$$(x, y)$$$ с $$$x_1 \le x \le x_2$$$, $$$y_1 \le y \le y_2$$$ для некоторых $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$.

Алиса хочет получить свою любимую раскраску с помощью этих операций. Какое наименьшее количество монет ей придется потратить? Можно показать, что всегда можно преобразовать исходную таблицу в любую другую.

Входные данные

Первая строка ввода содержит $$$2$$$ целых числа $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — размеры таблицы.

В $$$i$$$-й из следующих $$$n$$$ строк содержится строка $$$s_i$$$ длины $$$m$$$, состоящая из букв W и B. $$$j$$$-й символ строки $$$s_i$$$ - W, если клетка $$$(i, j)$$$ окрашена в белый цвет в любимой раскраске Алисы, и B, если она окрашена в черный цвет.

Выходные данные

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

Примеры
Входные данные
3 3
WWW
WBB
WBB
Выходные данные
2
Входные данные
10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW
Выходные данные
68
Примечание

В первом примере оптимально просто применить четвертую операцию один раз к прямоугольнику, содержащему клетки $$$(2, 2), (2, 3), (3, 2), (3, 3)$$$. Это обойдется в $$$2$$$ монеты.