Minimum Fuel Consumption under Time and Speed Constraints

In a city there are n north–south roads and n east–west roads that intersect to form a grid. The distance between any two adjacent parallel roads is L miles. The intersections are identified by coordinates: the southwest corner is (1,1) and the northeast corner is (n,n). At any intersection, one can change direction arbitrarily. Each road (regardless of travel direction) has its own speed limit which applies to the entire road.

You are given two intersections: a starting point (x_s, y_s) and a target (x_t, y_t). You must drive from the start to the target along a path that is a shortest route (i.e. a Manhattan shortest path). You are allowed to change the driving speed only at intersections. On each segment you travel along a road, you must obey that road’s speed limit. Moreover, your total travel time must lie within the closed interval \([t_1, t_2]\) (in hours).

The car’s speed, measured in miles per hour, must be a positive multiple of 5. If the car travels at speed \(v\), then its fuel efficiency on that segment is given by the formula \[ \text{Efficiency} = 80 - 0.03v^2 \quad \text{(miles per gallon)}. \] Thus, if a segment is of length L, the fuel consumed on that segment is \[ \frac{L}{80 - 0.03v^2} \quad \text{(gallons)}. \]

Your task is to choose both the Manhattan route and a speed for each segment (subject to that segment’s road speed limit and the multiple-of-5 rule) so that the overall fuel consumption is minimized while ensuring that the total travel time (the sum of times for all segments, where the time for a segment is \(L/v\)) is between \(t_1\) and \(t_2\) inclusive. Note that when a segment is traveled horizontally (east–west), the applicable speed limit is that of the east–west road corresponding to the current y-coordinate, and when a segment is traveled vertically (north–south), the applicable limit is that of the north–south road corresponding to the current x-coordinate.

If it is impossible to complete the trip under the given constraints, output -1. Otherwise, output the minimum total fuel consumption (in gallons) rounded to two decimal places.

inputFormat

The input consists of the following lines:

1. One line with two integers: n (number of roads in each direction) and L (distance between adjacent roads, in miles).
2. One line with two integers: x_s and y_s (the starting intersection coordinates).
3. One line with two integers: x_t and y_t (the target intersection coordinates).
4. One line with two decimal numbers: t1 and t2 (the lower and upper bounds for the total travel time, in hours).
5. One line with n integers: the speed limits (in mph) for the north–south (vertical) roads for x = 1 to n.
6. One line with n integers: the speed limits (in mph) for the east–west (horizontal) roads for y = 1 to n.

Note: The coordinates are 1-indexed. It is allowed that \(x_s > x_t\) and/or \(y_s > y_t\); in such cases, the movement is in the opposite direction but the rules remain the same.

outputFormat

If it is impossible to complete the trip under the given constraints, print -1. Otherwise, print the minimum fuel consumption (in gallons) rounded to two decimals.

sample

3 10
1 1
3 3
2.0 3.0
40 40 40
40 40 40

1.01