e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.

Увімкніть лампу

Степан розробляє електронну схему на прямокутній сітці розміром n * m. Усього n * m квадратних плиток. Два (з чотирьох) протилежних кута кожної плитки з'єднані дротом.

Джерело живлення під’єднано до лівого верхнього кута сітки, лампа - до правого нижнього. Для того щоб увімкнути лампу можна повернути будь-яку плитку на 90 градусів у обох напрямках.

На зображенні лампа вимкнута. Якщо повернути будь-яку плитку у другій колонці праворуч, то лампа ввімкнеться.

prb7403

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

Вхідні дані

Перший рядок містить два цілих числа n та m (1n, m500) - розміри сітки. Далі слідують n рядків по m символів - \ або /, що характеризують напрямлення дроту на даній плитці.

Вихідні дані

Вивести відповідь на задачу, або ж повідомлення "**NO SOLUTION**", в тому випадку, коли увімкнути лампу неможливо.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 5
\\/\\
\\///
/\\\\

Вихідні дані #1
1
Джерело 2015 ACM Ukraine, Перший етап, 25 квітня