e-olymp
Задачі

Шоколад

Шоколад

У Марічки та Зеника є прямокутна плитка смачного українського шоколаду. Плитка складається з однакових квадратиків, кожен з яких може бути або чорним, або білим.

Марічка проведе довільну (можливо, нульову) кількість повних горизонтальних (зліва направо) розрізів плитки, тоді як Зеник — довільну (можливо, нульову) кількість повних вертикальних (зверху вниз) розрізів. Зауважте, що розрізи можна проводити тільки між квадратиками плитки, а також що Зеник і Марічка можуть зробити різну кількість розрізів. Після проведення всіх розрізів плитка розпадеться на певну кількість прямокутних шматків, які наші герої певним чином розділять між собою.

Оскільки Зеник дуже любить чорний шоколад, він хоче, щоб після всіх розрізів кількість цілих шматків, які складаються виключно з чорних квадратиків, була якомога більшою. Марічка хоче цю саму кількість зробити якомога меншою. Зауважте, що героїв не цікавить, якого саме розміру будуть шматочки: головне — їхня кількість.

Щоб усе було чесно, Андрій окремо та незалежно запитає Марічку та Зеника, в яких саме місцях потрібно провести розрізи, а потім сам замість них проведе ці розрізи.

Завдання

Напишіть програму, яка за заданими розмірами плитки, а також типом кожного її одиничного квадратика визначить, скільки після всіх розрізань утвориться шматочків, що складаються виключно з чорних квадратиків, — за умови оптимальних дій обох героїв.

Вхіднідані

Перший рядок вхідного файла містить два цілих числа Nі M (2 ≤ N ≤ 1000, 2≤ M ≤ 1000): висоту та ширину плитки відповідно. Далі йдуть N рядків по M символів в кожному, які позначають тип відповідного одиничного квадратика шоколадки. Символ B позначає чорний квадратик, а символ W — білий.

Вихіднідані

Єдиний рядок вихідного файла повинен містити одне ціле число — кількість шматків, які складатимуться виключно з квадратиків чорного шоколаду.

Оцінювання

Набір тестів складається з 2 блоків:

1. 40 % балів: N ≤ 8, M≤8.

2. 60 % балів: на вхідні дані не накладають додаткових обмежень.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 4
BWBB
BBBW
BBBW
Вихідні дані #1
2
Джерело XXVIII Всеукраїнська олімпіада з інформатики 2015 р.