# The Bumpy Robot

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 h1 to an adjacent block of height h2, the amount of energy required is,  ⌈α1(h1−h2)⌉+γ, ifh1>h2 ∆E =  γ, if h1 = h2 ⌈α2(h2−h1)⌉+γ, ifh1<h2 and the amount of time required is,  ⌈β1(h1−h2)⌉+δ, ifh1>h2 ∆T =  δ, if h1 = h2 ⌈β2(h2−h1)⌉+γ, ifh1<h2 Here, α1, α2, γ, β1, β2 and δ 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 α1 and α2, and a positive integer γ. The second line contains two more positive floating point numbers β1 and β2, and another positive integer δ. 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 rs, cs, rt, ct and E, where (rs,cs) is the row, column numbers of the starting block, (rt, ct) 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 66 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

2/2 11665 66 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 00 Sample Output failed 112