Problem C - Mighty-Hero Competition

Super Heros from all over the galaxy are coming to town for their annual Mighty-Hero Competition(tm). This year's competition will be held as a race where Heroes jump from building to building. The race will take part in a very well organized part of the city, where buildings are distributed in a grid like structure. The only known property of each building is its height.

The race always start in the top left building of the selected town area and ends in the bottom right one. Super Heros are free to choose their path but have to be careful because when they jump down they lose energy and also because they have a limit on how much they can climb. If an hero reaches a negative energy level he dies.

Figure 1
Fig 1. - One possible scenario.

As usual, as the competition stirs a lot of enthusiasm, there are lot of betting offers for people wishing to guess the overall winner. Dr. What is a evil villain who is trying to take advantage of this, by determining the winner beforehand. For that he invented a machine that is capable of scanning the overall characteristics of each Super Hero:

Example: An hero with climbing capability of 3 can climb from a building of height 1 to one of height 4 but not to one of height 5. An hero with descent capability of 3 can jump from a building of height 7 to a building of height 4 without losing any energy, but if he jumps from the same building to a building of height 2 he will lose 2 points of energy.

The Problem

Dr. What wants you to create a program that can calculate the number of jumps each Super Hero takes to finish the race and the energy he will have at the end. You should assume that all Super Heroes have Super Intelligence and will always choose the quickest path. If two paths take the same number of jumps the Hero will chose the one that drains less energy.


The first line of the input file will contain information about the hero as three integers E, C and D: energy (0≤E≤300), climb ability (0≤C≤100) and descent ability (0≤D≤100). The second line will contain two integers C and L: the number of buildings in each grid line (1≤C≤200) and in each grid column (1≤L≤200). The next L lines will describe each line of the city. Each one of these lines will contain C integers containing the height H (1≤H≤300) of each building.


The output will be a single line containing two integers. The minimum number of jumps the Super Hero must use to reach the final building and the remaining energy. If two paths exist that require the same number of moves you should print the one that requires less energy spending. If the hero cannot complete the course without depleting his energy the output should be a single line containing the word impossible.

Sample Input 1

10 5 2
4 4
12 11 7 5
5 10 9 5
7 3 5 5
5 5 5 5

Sample Output 1

6 8

Sample Input 2

2 5 0 
4 4
12 11 7 5
5 10 9 5
7 3 5 5
5 5 5 5

Sample Output 2


TIUP & CPUP 2007
Universidade do Porto
(30 de Maio de 2007)