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

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

1 second
512 megabytes
Easy

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

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

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

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

Input

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

Output

Єдиний рядок вихідного файлу має містити відповідь на задачу, або ж повідомлення "NO SOLUTION", в тому випадку, коли увімкнути лампу неможливо.

Обмеження: 1 \leq N, M \leq 500.

Examples

Example 1

Loading
Loading

Scoring

В даній задачі дванадцять блоків. Тести нараховуються окремо за кожен блок, при умові проходження усіх тестів блоку. 40 балів можна отримати, якщо Ваша програма вірно працює при 1 \leq N \leq 4 та 1 \leq M \leq 5.