Problem Description

There are \( n \) north-south bidirectional streets and \( n \) east-west bidirectional streets intersecting each other. The distance between adjacent streets (regardless of direction) is \( L \) miles. The intersection at the southwest corner is labeled \( (1,1) \), and the northeast corner is \( (n,n) \). You can change driving directions at any intersection. Each street has its own speed limit, which applies to the entire street regardless of direction.

Your task is to drive from intersection \( (x_s, y_s) \) to \( (x_t, y_t) \), with the condition that you can only change speeds at intersections, must not exceed the speed limit of the street you are on, must follow the shortest route, and the travel time must be within the given closed interval \( [t_1, t_2] \). Speed is measured in miles per hour and must be a positive integer multiple of 5. If the speed is \( v \), the number of miles per gallon of gasoline is \( 80 - 0.03v^2 \).

Input Format

The first line of input contains two integers \( n \) and \( L \).
The second line contains \( n \) positive integers describing the speed limits of the east-west streets from south to north.
The third line contains \( n \) positive integers describing the speed limits of the north-south streets from west to east.
The fourth line contains six positive integers \( x_s, y_s, x_t, y_t, t_1, t_2 \).

Output Format

If there is no solution, output "No".

Otherwise, output two lines describing the earliest arrival plan (if multiple plans exist, choose the most fuel-efficient one) and the most fuel-efficient plan (if multiple plans exist, choose the earliest arrival one). Each plan is represented by two numbers: the first number is the arrival time (in minutes, rounded up); the second number is the fuel consumption (in gallons, rounded to two decimal places).

Sample Input and Output

Sample Input #1

6 20
30 40 50 50 50 50
50 50 50 50 50 40
1 1 6 6 300 320

Sample Output #1

300 6.25
318 5.60

Sample Input #2

8 2
10 20 20 30 10 20 10 10
10 20 20 30 10 20 10 20
6 8 2 4 10 39

Sample Output #2

No

Notes

In Sample 1, the fastest route is to travel at a constant speed of 40 miles per hour, covering a distance of 200 miles, thus taking 5 hours. Each gallon of gasoline can travel 80 - 0.03 * 40 * 40 = 32 miles, so the fuel consumption is 200 / 32 = 6.25 gallons.

The most fuel-efficient route is to travel 120 miles at 40 miles per hour and then 80 miles at 35 miles per hour, with a fuel consumption of 120 / 32 + 80 / (80 - 0.03 * 35 * 35) = 5.60 gallons. The diagram below shows a route that satisfies both plans (with the second plan requiring a speed change at (6,2)).

20% of the test cases satisfy: \( n \leq 4 \)

50% of the test cases satisfy: \( n \leq 8 \)

100% of the test cases satisfy: \( 1 \leq n \leq 10 \), \( 1 \leq L \leq 20 \), \( 0 \leq t_1 \leq t_2 \leq 1000 \). Speed limits do not exceed 50.

见题面 Input 部分

见题面 Output 部分