**Languages that can be used:
c, java, cpp, cc** **to be compiled in UNIX platform - so please make sure they compile on a unix compiler (such as gcc) before submitting the final version to me.**
There is a city whose streets are arranged in a grid in which north-south, east-west streets are separated by gaps of 10miles each. As shown in the above diagram
All streets are two-way. Entrance and exit ramps connect the streets at every intersection.
The speed limits are separately posted for each street and are the same for the entire street in both directions.(10, 20, 30...60mph)
In the illustration above, the southwestern corner of the grid is (1, 1), the southeastern corner is (6, 1), and so on.
Fuel consumption of a car is given in miles-per-litre (mpl) and depends on speed of the car.
Speed of a car is given in mile-per-hour (mph) and is always a positive integer multiple of 5.
The formula relating mpl(mile-per-litre) to mph (mile-per-hour) is a very simple one:
**A car travelling at *v* mph makes 80 - 0.03 **v*2 mpl.**
In a given grid of streets we would like to travel from intersection (*xs*,*ys*) to intersection (*xt*, *yt*).
You have to develop a program to determine the most fuel efficient way of making the trip such that:
* the car does not change speed between intersections,
* the car obeys all speed limits,
* the car travels the shortest possible distance between the start and finish, and
* the car arrives at the destination within a specified travel interval.
An intersection means a point in the grid where two streets meet. For example, the point where 2nd horizontal street and 5th vertical street is an intersection which is defined as (5,2).
A car will travell at the same speed between two adjacent intersections. In the given example, the car may travel at a speed 10 mph between (2,2) and (2,3) which is an interval of the 2nd vertical street. The car can then travel a speed 15 mph between (2,3) and (2,4), and then travel a speed 10 mph between (2,4) and (3,4), .... etc.
The data occupy 5 lines. The first line contains an integer
*n*<=10 which is the number of horizontal and vertical streets. The second line contains an integer which is the grid unit size in miles, smaller than 100. The third and fourth lines contain *n* integers each, specifying the speed limits on the horizontal and vertical streets, respectively. The largest speed limit is 50. The last line of data contains 6 integers. The first four are *xs*, *ys*, *xt*, and *yt*. The last two integers give the shortest and the longest allowed time to travel in minutes, inclusive, both not bigger than 1000.
The output consists of one line in the format given in the sample outputs.
If the travel is possible then the output reports the earliest arrival time (but within the imposed limits) that consumes the minimum amount of fuel. The time is to be reported in minutes (integer), rounded up.
If the travel is not possible, then the output contains a single word IMPOSSIBLE.
### Example DATA
#### 1.0 Input:
10 20 30 40 50 50 50 50
50 50 50 50 50 50 40 50
2 3 7 8 300 320
The economical travel: 318 minutes, fuel 5.60 liters
#### 2.0 Input
10 20 20 30 10 20 10 10
10 20 20 30 10 20 10 20
6 8 2 4 10 39
#### 2.0 Output
#### 3.0 Input
30 20 20 10 10 20 10 10 20 20
40 20 10 20 10 20 20 10 10 20
1 1 10 10 100 500
#### 3.0 Output
The economical travel: 498 minutes, fuel 2.76 liters
All code must be **well commented** with a short description of functions implemented.
Please only bid if you are ready for this challenge and can implement the solution in time. Its really straight forward, just requires a bit of thinking.
### An extra $$$ bonus will also be paid to the bidder if the solution is impressive!
Only bid on this if you are sure you can implement the CORRECT solution.
Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):
All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).
Unix, Linux ONLY. Please make sure your program compiles on a unix compiler!