Problem B

The Bumpy Robot

Input:standard input

Output: standard output

 

The bumpy robot moves around an M ´ N grid of square blocks. Each block has an integral height. To move from a block of height h₁ to an adjacent block of height h₂, the amount of energy required is,

 

                     

 

and the amount of time required is,

 

                     

 

Here, a₁, a₂, g, b₁, b₂ and d are some known constants.

 

The bumpy robot must move from a given starting block to a target block in minimum amount of time that is possible without consuming more than a given amount of energy. Please help him find out whether it is possible for him to move to the target block under the given constraint and if possible to determine the minimum amount of time required for reaching there.

 

Note that two blocks are assumed to be adjacent if they have a side in common.

 

 

Input

The input may contain multiple test cases. Each test case begins with a line containing two integers M and N (1<=M, N <=15). The second line contains two positive floating point numbers a₁ and a₂, and a positive integer g. The second line contains two more positive floating point numbers b₁ and b₂, and another positive integer d. Then follow M lines containing N integers each giving the height of the corresponding block in the grid. The top-left corner of the grid is assumed to be in row 1 and column 1. The next line contains five integers r_s, c_s, r_t, r_t and E, where (r_s, c_s) is the row, column numbers of the starting block, (r_t, c_t) is the row-column number of the target block and E (1 <= E<= 200) is the energy constraint for the bumpy robot.

 

A test case containing two zeros for M and N terminates the input.

 

Output

For each test case in the input file print a line containing the minimum time required if the target is reachable, print "failed" otherwise.

 

Sample Input

6 6
3.2 1.2 3
5.0 2.0 2
5 -7 10 25 6 23
1 7 9 -2 20 2
12 -10 2 6 9 22
11 19 -20 4 8 0
2 2 6 8 10 12
12 10 2 3 6 9
1 1 6 6 5
6 6
1.5 0.2 1
0.2 1.5 1
5 10 20 25 30 43
15 -7 30 34 40 50
20 35 -10 40 45 55
30 35 45 -20 50 57
40 42 48 50 -25 60
50 55 60 63 68 -30
1 1 6 6 200
0 0

 

Sample Output

failed
112