Grid Speed

Consider a grid-shaped city in which the north–south streets run on an elevated level above the east–west streets. Adjacent parallel streets are a fixed number of miles apart. Every street is two-way, and on- and off-ramps connect the two levels at every intersection, so switching between a north–south street and an east–west street takes no time. There are no traffic lights and almost no traffic.

Each street has its own speed limit, which is the same along the whole street and in both directions. Label an intersection by its column and row numbers, so the south-west corner is $(1, 1)$ and, in an $n \times n$ grid, the south-east corner is $(n, 1)$.

Fuel economy depends on speed. A car's speed is always a positive integer multiple of $5$ miles per hour (mph). A car travelling at $v$ mph gets $80 - 0.03\,v^2$ miles per gallon (mpg).

For one trip from intersection $(x_s, y_s)$ to intersection $(x_t, y_t)$ you must choose the speed on every segment so that:

• the car keeps a constant speed between two consecutive intersections (it may change speed only at an intersection);
• the car never exceeds the speed limit of the street it is currently on;
• the car travels the shortest possible distance between start and finish (that is, it never moves away from the destination); and
• the car arrives within the allowed time interval.

For each trip, determine both the fastest way to arrive and the most fuel-efficient way to make the trip.

The first line contains an integer $t$, the number of scenarios.

Each scenario is given on five lines:

1. an integer $n$ ($n \le 10$), the number of east–west streets and also the number of north–south streets;
2. an integer $g$ ($g < 100$), the spacing between adjacent parallel streets, in miles;
3. $n$ integers: the speed limits of the east–west (horizontal) streets, from row $1$ to row $n$;
4. $n$ integers: the speed limits of the north–south (vertical) streets, from column $1$ to column $n$;
5. six integers $x_s\ y_s\ x_t\ y_t\ a\ b$: the start column and row, the target column and row, and the smallest and largest allowed travelling times $a \le b$ in minutes (inclusive).

The largest speed limit is $50$. Both $a$ and $b$ are at most $1000$.

For each scenario, first print the line

Scenario k:

where $k$ is the scenario number starting from $1$.

If the trip cannot be completed within the allowed time interval, print a single line

IMPOSSIBLE

Otherwise print two more lines. On the second line, report the earliest arrival time that lies within the allowed interval, together with the least fuel needed to arrive at that time:

The earliest  arrival: T minutes, fuel F gallons

On the third line, report the smallest amount of fuel that can be used while still arriving within the interval, together with the earliest arrival time that uses that little fuel:

The economical travel: T minutes, fuel F gallons

Every arrival time $T$ is an integer number of minutes, rounded up. Every fuel amount $F$ is printed with exactly two digits after the decimal point. The spacing and punctuation must match the format above exactly (note the two spaces after earliest).