Minimizing Travel Cost Between Cities

During the summer vacation, Car in city A wants to visit a city B with his friends. In each city, there are 4 airports located at the vertices of a rectangle. Within the same city, every pair of airports is connected by a straight highway railway, with the cost per unit distance in city i being \( T_i \). Between any two different cities, every pair of airports is connected by an air route with the same unit cost \( t \).

You are given \( n \) cities. For each city, you are given its highway cost \( T_i \) and the coordinates of two opposite corners of the rectangle (\( x_1, y_1, x_2, y_2 \)); the four airports of the city are located at \( (x_1,y_1), (x_1,y_2), (x_2,y_1) \) and \( (x_2,y_2) \). Car can choose any airport in the departure city A and any airport in the destination city B. He can also reposition within a city using the highway railway. The cost to travel between two airports in the same city is \( T_i \) multiplied by the Euclidean distance between them, while the cost to travel between airports in different cities is \( t \) multiplied by the Euclidean distance.

Find a route from some airport in city A to some airport in city B (possibly using highway transfers within the cities) such that the total cost is minimized.

The answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

inputFormat

The first line contains four numbers: \( n\) (the number of cities), \( t \) (the unit flight cost), \( A \) and \( B \) (the indices of the departure and destination cities respectively, 1-indexed).

Then \( n \) lines follow. The i-th of these lines contains five numbers: \( T_i \), \( x_1 \), \( y_1 \), \( x_2 \), \( y_2 \), where \( T_i \) is the unit highway cost in city i, and \( (x_1,y_1) \) and \( (x_2,y_2) \) are coordinates of two opposite corners of the rectangle representing city i.

outputFormat

Output a single number — the minimum total cost to travel from city A to city B. The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

2 1 1 2
2 0 0 1 1
3 2 2 3 3

1.4142135624