Задача №111546. Лихолесье

Олимпиада завершена. Режим дорешивания.

Тринадцать гномов и хоббит заблудились в Лихолесье. К счастью, они вспомнили, что Гендальф дал им карту. Но чтобы успеть к логову дракона вовремя, им надо поторопиться. Карта включает в себя N*M квадратов, в каждом из которых нарисован лес, дорога, болото или грязь. Чтобы пройти через дорогу, надо потратить 1 час, через грязь - 2 часа, через лес - 3 часа. Через болото идти нельзя. Пройти можно только в соседнюю клетку. Ходить по диагонали нельзя. При этом нельзя три раза подряд пройти через лес, так как он очень густой и там очень легко потеряться. Вам необходимо написать программу, которая определит минимальное время прохождения маршрута.

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

Вводится два числа N и M – количество квадратов в ширину и в длину (1 ≤= N, M ≤= 30). Затем вводится карта из M строк и N столбцов, на которой B – точка в которой сейчас стоят гномы, E – точка в которую надо попасть, W – дорога, F – лес, D – грязь, а S – болото.

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

Выведите минимальное время прохождения маршрута.

Примеры
Входные данные
6 3
WWDFFE
DFSFSS
BWWWWW
Выходные данные
12
Сдать: для сдачи задач необходимо войти в систему