Problem Description

Agent Karol is driving his red car on a three-lane highway. In front of him there are some cars, and all of them are moving forward at a fixed speed that depends on the lane: the speed of lane $i$ is $v_i$, and $v_1 > v_2 > v_3$. Other cars never change lanes or speed, but Karol can change lanes instantly, and can also instantly change his own speed to any real value not exceeding $v_0$. He cannot turn around, so his speed is within the interval $[0, v_0]$.

Including Karol, every car has length $1$. Cars may collide with each other, but Karol must not allow any two cars to collide, i.e., they must not overlap with a positive-length intersection. Formally, define a car’s position as the distance between its front bumper and the start of the highway (i.e., Karol’s initial position). For two cars in the same lane, the difference of their positions must not be less than $1$.

Near the entrance there is a road segment of length $L$, and Karol is currently at the start of the third lane. The highway extends infinitely, and outside the described segment there are no cars on the highway.

Compute the minimum time after which Karol can overtake all cars. In other words, compute the minimum time after which every other car can be completely behind Karol’s rear bumper.

Note: Karol may change his lane and speed at non-integer times, and car positions may also be non-integers.

Input Format

The first line contains five integers $L, v_0, v_1, v_2, v_3$.

The next three lines contain strings $s_i$ of length $L$. Line $i$ describes lane $i$: if the $j$-th character of $s_i$ is #, then there is a car at that position; if it is ., then there is no car at that position. It is guaranteed that the first characters of $s_1$ and $s_2$ are ., and the first character of $s_3$ is #, which represents Karol’s car. There are at least two # characters in the input.

Output Format

Output one real number: the minimum time needed for Karol to overtake all cars.

Any output with absolute or relative error within $10^{-9}$ compared to the standard answer will be accepted. That is, if your answer is $x$ and the standard answer is $x_0$, then your output is considered correct if $\frac{|x - x_0|}{\max(x_0, 1)} \leq 10^{-9}$.

5 60 15 10 9
.#...
..#.#
###..

0.644444444444444

6 140 120 115 110
.##...
......
#.#.#.

0.166666666666667

Hint

Constraints: for $100\%$ of the testdata, $2 \leq L \leq 2 \times 10^5$, $1 \leq v_3 < v_2 < v_1 < v_0 \leq 140$.

Translated by ChatGPT 5