1009 - Fat Cat

Time limit : 1 sMemory limit : 32 mb
Submitted : 2414Accepted : 759

Problem Description

Fat cat's duty is to catch mice, and it controls several rooms arranged in a matrix in which mice often come. Now a mouse comes into this room matrix and digs many many holes, and the mouse is cunning and it knows that fat cat will sleep in the daytime, so it goes out for food in that time instead of at night. Fat cat has to put some cheese in each room to make it out.

The mouse always appears first at room(0,0), and it will turn to another room near the current room which has the most number of cheese after it eats up the cheese in the room. If there is no adjacent room or the number of cheese is 0 in every adjacent room, the mouse quickly run in a hole after it eats the cheese and fat cat can't catch it.

When the mouse and the cat arrive at the same room or the mouse turns to a room where the cat is at the same time, the cat can catch the mouse!

When the mouse first appears, fat cat is in room(i,j)(not in room(0,0)),and it wants to catch the mouse as quickly as it can before the mouse runs away. We suppose that both the cat and the mouse move only vertically or horizontally 1 step in each time period.

Now it's your turn to write a program to calculate how many steps at least fat cat should move to catch the mouse. For example: the mouse starts at room(0,0), and fat cat is in room(2,0) at the same time. And the mouse moves to room(0,1),while fat cat can go to either room(2,1) or room(1,0), or just stay there.


the input contains mutiple cases. The first line of each case consists of two positive integer: n and m (1&ltn&lt=100,1&ltm&lt=100),showing that the room matrix has n rows and m columns rooms. Then will be n rows non_negative integers presenting the number of cheese in each room(there are no two rooms have the same positive number of cheese). Each row has m integers. The following row shows fat cat's initial position: row i and column j.


for each case,print the minimum number of time period fat cat uses to catch the mouse in a single line. If the mouse run away before being caught, print "impossible" instead.

Sample Input

2 2
15 3
2 4
0 1
3 3
1 5 9
3 7 0
2 4 6
2 0

Sample Output