B. Газонокосилка
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

У вас есть сад, в котором растет трава и сорняки. Ваш сад представляет собой клетчатое поле размером n × m. Строки пронумерованы от 1 до n сверху вниз, а столбцы — от 1 до m слева направо. Каждая клетка обозначается парой (r, c), где r — номер строки, в которой расположены клетка, а c — номер столбца. Каждая клетка содержит либо траву, либо сорняк. Например, сад размера 4 × 5 может выглядеть следующим образом (пустые клетки обозначают траву):

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

За один ход вы можете сделать одно из двух:

1) Пойти на одну клетку в ту сторону, куда вы смотрите.

  • если вы смотрите направо: пойти из клетки (r, c) в клетку (r, c + 1)

  • если вы смотрите налево: пойти из клетки (r, c) в клетку (r, c - 1)

2) Пойти на одну клетку вниз (то есть из клетки (r, c) в клетку (r + 1, c)) и развернуться в другую сторону.

  • если вы смотрели направо, вы будете смотреть налево

  • если вы смотрели налево, вы будете смотреть направо

Вы не можете выходить за пределы поля. Чтобы скосить сорняк, вы должны оказаться в одной клетке с ним (при этом не имеет значения, в какую сторону вы смотрите). На это действие ход не тратится.

Какое наименьшее количество ходов потребуется, чтобы скосить все сорняки?

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

В первой строке содержится два целых числа n и m (1 ≤ n, m ≤ 150) — количество строк и столбцов соответственно. Далее следует n строк по m символов в каждой — описание сада. «G» обозначает, что данная клетка содержит траву. «W» обозначает, что данная клетка содержит сорняк.

Гарантируется, что верхняя левая клетка поля содержит траву.

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

Выведите одно целое число — минимальное количество ходов, которое требуется, чтобы скосить все сорняки.

Примеры
Входные данные
4 5
GWGGW
GGWGG
GWGGG
WGGGG
Выходные данные
11
Входные данные
3 3
GWW
WWW
WWG
Выходные данные
7
Входные данные
1 1
G
Выходные данные
0
Примечание

В первом примере начальное состояние поля выглядит следующим образом:

Одно из возможных решений: