Overtaking on the Highway

Agent Karol is driving his red car on a three‐lane highway. In front of him there are several vehicles, each moving at a fixed speed determined by its lane. Specifically, cars in lane \(i\) move at speed \(v_i\) with \(v_1 > v_2 > v_3\). None of these vehicles change lanes or speeds. In contrast, Karol can instantly change lanes and adjust his speed to any real number in the range \([0, v_0]\) (i.e. he cannot exceed \(v_0\)).

All vehicles (including Karol’s) have a length of 1. The position of a car is defined as the distance from the start of the highway (which is Karol’s starting point) to its head. Thus, a car with head at position \(x\) occupies the interval \([x-1, x]\). To avoid collisions, any two different cars on the same lane must maintain a head-to-head distance of at least 1 (i.e. they must not have an overlapping interval of positive length).

At the highway entrance there is a road segment of length \(L\). Karol starts at the beginning of this segment on lane 3. The highway beyond the described segment is empty (i.e. there are no vehicles there).

Your task is to compute the minimum time after which Karol can be guaranteed to have overtaken all other vehicles. In other words, find the smallest time \(T\) such that at time \(T\) every other vehicle’s head is strictly behind Karol’s car tail.

Note: Karol may change lanes and speeds at non‐integer times, and car positions may be non‐integer as well. It is guaranteed that \(v_0 > v_1\), so overtaking is always possible.

Hint: If Karol immediately accelerates to \(v_0\), his head will be at position \(v_0t\) at time \(t\), and his tail will be at position \(v_0t-1\). A vehicle in lane \(i\) with initial head position \(p\) moves at constant speed \(v_i\) and will have its head at position \(p+v_it\) at time \(t\). Thus, to have overtaken a certain vehicle, the following condition must hold:

[ v_0t - 1 > p + v_i t \quad \Longleftrightarrow \quad t > \frac{p+1}{v_0-v_i}. ]

The answer is the maximum over all vehicles of \(\frac{p+1}{v_0-v_i}\).

inputFormat

The input begins with a single line containing six numbers:

n L v0 v1 v2 v3

Here,

• n is the number of vehicles in front of Karol,
• L is the length of the highway entrance segment,
• v0 is Karol’s maximum speed, and
• v1, v2, v3 are the speeds of lanes 1, 2, and 3 respectively with \(v_1 > v_2 > v_3\).

Each of the next n lines contains two numbers:

lane position

where lane is an integer (1, 2, or 3) indicating the lane of the vehicle, and position is a real number representing the distance from the highway start to the vehicle’s head. It is guaranteed that each vehicle is ahead of Karol (i.e. position > 0), and cars on the same lane are at least 1 unit apart.

outputFormat

Output a single real number, the minimum time after which every vehicle’s head is strictly behind Karol’s car tail. Your answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 100 120 100 80 60
1 10
2 20
3 30

0.55

</p>