Лето 3

Город, в котором живет Петя имеет вид прямоугольника, улицы в нем образуют сетку `M`x`N`. Перед каждым перекрестком на подъезде к нему может стоять дорожный знак. Также знак может стоять после перекрестка у въезда на улицу.

В городе встречаются следующие виды дорожных знаков: знаки, установленные перед перекрестком – поворот только направо (R), поворот только налево (L), только проезд прямо (F), поворот налево запрещен (NL), поворот направо запрещен (NR), проезд прямо запрещен (NF); знаки, установленные после перекрестка – проезд запрещен (S), максимальная скорость до ближайшего перекрестка – `X` км/ч. (!`X`). В отсутствие ограничивающего знака максимальная скорость равна `Y` км/ч. Длина всех улиц одинакова и равна `L` метров. Разворачиваться на перекрестке и ехать в строго противоположном направлении не разрешается.

Петя живет в доме около перекрестка, где пересекаются `x_s`-я вертикальная и `y_s`-я горизонтальная улицы (улицы нумеруются, начиная с 1). Петин папа работает на заводе около перекрестка, где пересекаются `x_d`-я вертикальная и `y_d`-я горизонтальная улицы. Помогите Пете выяснить, какое минимальное время требуется папе, чтобы доехать на работу, если Петин папа – законопослушный водитель и соблюдает все правила дорожного движения.

Первая строка ввода содержит целые числа `M,\ N\ (1\ ≤\ M,\ N\ ≤\ 20),\ Y\ (1\ ≤\ Y\ ≤\ 80),\ L\ (1\ ≤\ L\ ≤\ 10000),\ "xs",\ "ys",\ "xd"` и `"yd"\ (1\ ≤\ "xs",\ "xd"\ ≤\ N,\ 1\ ≤\ "ys",\ "yd"\ ≤\ M,\ ("xs",\ "ys")\ ≠\ ("xd",\ "yd"))`.

Следующие `M⋅N` строк содержат информацию о знаках, расположенных на соответствующих перекрестках (порядок перечисления перекрестков следующий: сначала идут перекрестки, расположенные на 1-й горизонтальной улице, в возрастающем порядке номеров вертикальных улиц, затем перекрестки, расположенные на 2-й горизонтальной улице, и т.д.)

Формат информации о знаках следующий: описания знаков разделяются запятыми, сначала идет буква латинского алфавита, означающая направление, в котором уходит с перекрестка улица, на которой стоит знак, затем после двоеточия идет обозначение знака (направления обозначаются буквами N, S, E и W – см. рисунок). После последнего знака идет точка. По типу знака понятно, находится он до или после перекрестка. Ограничение скорости – целое число, `1\ ≤\ X\ ≤\ 80`.

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

3 4 60 5000 2 2 4 3
.
.
S:NL.
.
E:L.
N:S,E:S,S:S,W:!25.
S:NR.
.
.
E:!72,N:!80,W:!15.
E:!10.
.

3070