beecrowd | 2778

Dabriel's Matrix

By Gabriel Duarte, UFF BR Brazil

Timelimit: 1

Dabriel loves to create quirky games with her incredible matrices. The last game created ended up having a much higher complexity than the others and as he is very busy with the college, he asked for your help to develop a program capable of saying the answer of the game. It consists of a matrix N by M, where it is desired to leave the position (1,1) and reach the position (N,M) and each cell has a value and this value is increased in the total cost of the path for every visited cell. Your task is to find the cost of the smallest path. However, as it is about Dabriel the game is not so simple, some rules were imposed:

  1. Being in a cell (i,j) we can only go to the cells (i+1,j), (i,j+1) or (i,j-1);
  2. No cell can be visited more than once;
  3. It is not allowed to go through more than X cells with null values;
  4. It is not allowed to go through more than Y cells with negative values;

Dabriel knows that with so many rules can exist cases where there is no such path, so he will be satisfied if you print "Impossivel" for such cases. But one thing Dabriel can assure you: the cell (N,M) will always have a value greater than zero.


The input is composed of several test cases. The first line will have 4 integers N, M, X, Y (1 ≤ N, M ≤ 100, 0 ≤ X, Y ≤ 20). In the next N lines will have integers Xij (-100 ≤ Xij ≤ 100), representing the values of the cells of the matrix.


For each test case print the smallest path as described in the text, in cases where there is no response, print "Impossivel", without quotation marks.

Input Sample Output Sample

3 4 2 2
1 2 -5 -50
0 0 -1 -1
-50 0 5 2
3 4 1 1
1 2 -5 -50
0 0 -1 -1
-50 0 5 2
3 3 0 9 
-1 -1 -1
-1 -1 -1
-1 -1 -1