Mr. Frog lives in a grid-like marsh of rectangular shape, composed of equally-sized cells, some of which are dry, some of which are only watery places. Mr. Frog lives in a dry cell and can jump only from a dry cell to another dry cell on his wanderings around the marsh.
Mr. Frog wants to visit his girlfriend, Ms. Toad, who also lives in a dry cell in the same marsh. But Mr. Frog is lazy, and wants to spend the minimum amount of energy in his jumping way to Ms. Toad’s home. Mr. Frog knows how much energy he spends in any of his jumps. For any single jump, Mr. Frog always uses the following figure to determine which are the possible target cells from his current position (the cell marked $\texttt{F}$), and the corresponding energy spent in the jump, in calories. Any other cell is unreachable from Mr. Frog’s current position with a single jump.
Your task is to determine the minimum amount of energy that Mr. Frog needs to spend to get from his home to Ms. Toad’s home.
Output
For each test case in the input, your program must produce one line of output, containing the minimum calories consumed by Mr. Frog to go from his home location to Ms. Toad’s home location. If there is no way Mr. Frog can get to Ms. Toad’s home, your program should output $\texttt{impossible}$.
The output must be written to standard output.