Вася сделал покупки в популярном торговом центре и теперь хочет отправиться домой. Для этого ему сначала нужно выехать на своей машине с парковки. Задача эта не очень простая, поскольку на парковке находится множество машин других посетителей торгового комплекса. Сама же парковка представляет собой прямоугольную область N × M клеток. В одной из клеток находится машина Васи. В других клетках могут находиться машины остальных покупателей. Кроме того, в некоторых клетках (по крайней мере, в одной) находятся выезды с парковки.
Вася хочет доехать до одного из выездов с парковки. Вася может перемещаться на машине из текущей клетки в соседнюю по стороне клетки, если эта клетка находится на парковке и свободна от других машин. В процессе переезда Вася может увеличивать скорость автомобиля максимум на A или уменьшать скорость автомобиля максимум на B. Итого, если до переезда скорость автомобиля была равна V, то после переезда на новую клетку скорость может быть любым (не обязательно целым) числом в интервале [V - B, V + A] по желанию Васи, с единственным ограничением — скорость не может быть ниже 1. Если в начале переезда скорость машины была равна V1, а после — стала равна V2, то будем считать, что Вася потратил 2 / (V1 + V2) времени на переезд. Кроме того, Вася может менять направление движения, только если скорость автомобиля равна 1. Это значит, что если Вася уже совершил переезд из одной клетки в другую и его скорость после переезда больше 1, то он может продолжать двигаться только в том же направлении. Если же следующая клетка в этом направлении занята машиной или находится за пределами парковки, то такое движение запрещено. Однако приезжать к выезду с парковки можно на любой скорости (даже если следующая клетка в направлении движения занята).
Определите, за какое наименьшее время Вася сможет добраться до какого-либо из выездов с парковки. Покидать парковку, выходя за пределы исходной области N × M, запрещено. Машины других покупателей не двигаются. Начальная скорость машины Васи равна 1.
В первой строке входного файла находятся 4 целых числа — размеры парковки N и M (1 ≤ N, M ≤ 200), а так же числа A и B (1 ≤ A, B ≤ 100). Следующие N строк описывают начальное состояние парковки. Каждая строка имеет длину M и состоит из символов '_._', '_C_', '_V_', '_E_'. Символ '_._' соответствует пустой клетке парковки, '_C_' — занятой автомобилем, '_V_' — клетка, в которой находится машина Васи, '_E_' — клетки, представляющие собой выезды с парковки. Гарантируется, что присутствует ровно один символ '_V_', не менее одного символа '_E_' и что Вася может добраться хотя бы до одного выезда с парковки.
Вывести единственное вещественное число с абсолютной или относительной погрешностью, не превышающей 10 - 6 — минимальное время, за которое Вася сможет добраться до одного из выездов с парковки.
В первом примере Вася при переезде с клетки (1, 1) в клетку (1, 2), содержащую выезд с парковки, может увеличить скорость с 1 до 3. При этом он потратит время, равное 2 / (1 + 3) = 0.5.
Во втором примере оптимально двигаться из клетки (1, 1) в клетку (1, 2), увеличив скорость до 2. Затем — в клетку (1, 3), снизив скорость до 1 из-за поворота. Далее — в клетку (2, 3), увеличив скорость до 2. Итого, будет потрачено время 2 / (1 + 2) + 2 / (2 + 1) + 2 / (1 + 2) = 2.
В третьем примере нельзя двигаться так же, как в предыдущем, поскольку клетка (1, 2) занята другой машиной. Необходимо двигаться сначала в клетку (2, 1) на скорости 1, затем повернуть на клетку (2, 2), увеличив скорость до 2, далее — в клетку (2, 3), увеличив скорость до 3. Итого, Вася потратит единиц времени.
## Входные Данные
В первой строке входного файла находятся 4 целых числа — размеры парковки N и M (1 ≤ N, M ≤ 200), а так же числа A и B (1 ≤ A, B ≤ 100). Следующие N строк описывают начальное состояние парковки. Каждая строка имеет длину M и состоит из символов '_._', '_C_', '_V_', '_E_'. Символ '_._' соответствует пустой клетке парковки, '_C_' — занятой автомобилем, '_V_' — клетка, в которой находится машина Васи, '_E_' — клетки, представляющие собой выезды с парковки. Гарантируется, что присутствует ровно один символ '_V_', не менее одного символа '_E_' и что Вася может добраться хотя бы до одного выезда с парковки.
## Выходные Данные
Вывести единственное вещественное число с абсолютной или относительной погрешностью, не превышающей 10 - 6 — минимальное время, за которое Вася сможет добраться до одного из выездов с парковки.
## Примеры
Входные данные2 2 2 2VE..Выходные данные0.500000000Входные данные2 3 1 1V....EВыходные данные2.000000000Входные данные2 3 1 1VC...EВыходные данные2.066666667
## Примечание
В первом примере Вася при переезде с клетки (1, 1) в клетку (1, 2), содержащую выезд с парковки, может увеличить скорость с 1 до 3. При этом он потратит время, равное 2 / (1 + 3) = 0.5.Во втором примере оптимально двигаться из клетки (1, 1) в клетку (1, 2), увеличив скорость до 2. Затем — в клетку (1, 3), снизив скорость до 1 из-за поворота. Далее — в клетку (2, 3), увеличив скорость до 2. Итого, будет потрачено время 2 / (1 + 2) + 2 / (2 + 1) + 2 / (1 + 2) = 2.В третьем примере нельзя двигаться так же, как в предыдущем, поскольку клетка (1, 2) занята другой машиной. Необходимо двигаться сначала в клетку (2, 1) на скорости 1, затем повернуть на клетку (2, 2), увеличив скорость до 2, далее — в клетку (2, 3), увеличив скорость до 3. Итого, Вася потратит единиц времени.
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ be the dimensions of the parking grid.
Let $ A, B \in \mathbb{Z}^+ $ be the maximum speed increase and decrease per move, respectively.
Let $ G = (V, E) $ be a grid graph of size $ N \times M $, where each cell $ (i, j) $ is a vertex.
Let $ S \subset V $ be the set of cells containing obstacles (cars), represented by 'C'.
Let $ V_0 \in V $ be the unique starting cell (marked 'V').
Let $ E_{\text{out}} \subset V $ be the set of exit cells (marked 'E').
Each cell is either:
- Free ('.') — traversable,
- Obstacle ('C') — blocked,
- Start ('V') — initial position,
- Exit ('E') — target.
Let $ v \in \mathbb{R}^+ $ denote the current speed of Vasya’s car, with $ v \geq 1 $.
Initial speed: $ v = 1 $.
**Constraints**
1. Movement is allowed only to adjacent (up/down/left/right) free or exit cells.
2. From speed $ v $, after a move, new speed $ v' \in [v - B, v + A] \cap [1, \infty) $.
3. Direction change is allowed **only** if current speed $ v = 1 $.
4. Once speed $ v > 1 $, movement must continue in the same direction until an exit is reached or blocked.
5. Exiting the grid is forbidden; exits are within $ [1, N] \times [1, M] $.
6. Time to move from cell with speed $ v_1 $ to adjacent cell with speed $ v_2 $: $ \frac{2}{v_1 + v_2} $.
7. Upon reaching any exit cell, the journey ends, regardless of speed or direction.
**Objective**
Find the minimum total time to reach any cell in $ E_{\text{out}} $ from $ V_0 $, obeying movement and speed constraints.
Formally, define state $ (i, j, v, d) $, where:
- $ (i, j) \in \{1, \dots, N\} \times \{1, \dots, M\} $: current position,
- $ v \in \mathbb{R}^+ $: current speed, $ v \geq 1 $,
- $ d \in \{(0,1), (1,0), (0,-1), (-1,0)\} \cup \{ \text{none} \} $: current direction (or undefined if at start).
Initial state: $ (i_0, j_0, 1, \text{none}) $, where $ (i_0, j_0) = V_0 $.
Goal: reach any $ (i, j) \in E_{\text{out}} $.
Transition: from state $ (i, j, v, d) $, if $ d = \text{none} $ (start), can choose any valid direction $ d' $ and any $ v' \in [1, 1 + A] $, move to neighbor $ (i', j') $ in direction $ d' $, cost $ \frac{2}{1 + v'} $.
If $ d \neq \text{none} $:
- If $ v = 1 $: may change direction to any valid $ d' $, and choose $ v' \in [1, 1 + A] $, move to $ (i', j') $ in direction $ d' $, cost $ \frac{2}{v + v'} $.
- If $ v > 1 $: must continue in direction $ d $, choose $ v' \in [v - B, v + A] \cap [1, \infty) $, move to $ (i', j') $ in direction $ d $, cost $ \frac{2}{v + v'} $.
Minimize total cost over all paths from initial state to any exit state.