War (1000 points)

You are the commander of an army and you have a map of the battle field. The map consists of the description of the terrain, a list of the enemy bases which have to be conquered and a list of units which are at your disposal.

The terrain is very diverse full of trenches. It is divided into NxM cells and for each cell it is known how long does it take for a unit to get through it. The terrain description consists of N lines containing M characters each. The jth character of the ith row is one of '1'...'9' and describes the time it takes for a unit to move from the [i][j] cell to one of its neighbors ([i+1][j], [i-1][j], [i][j+1] or [i][j-1]).

  

There are B enemy bases. The i,j coordinates of each base are given on a separate line (1 <= i <= N, 1 <= j <= M).

You have U units, each one is described on a separate line. A unit description starts with 3 integers X, Y and Q. (1 <= X <= N, 1 <= Y <= M, 1 <= Q <= B). X and Y are the coordinates of the unit. The description contains Q more integers V1, V2, ..., VQ showing which base the unit can conquer. The unit can only conquer one of these bases. (Enemy bases are numbered from 1 to B in the order they appear in the enemy base list).

Your job is to tell your boss the minimum amount of time required to conquer all the enemy bases. If it is impossible tell him so.

Input

The input contains multiple test cases. Each test case is as follows:

The last line of the input contains 0 0 0 0.

Output

The output should contain one line for each test case. Each line should contain one integer, the time that is required to conquer the enemy bases or -1 if it is impossible.

Notes:

Example input

3 4 4 4
1231
9299
1211
1 1
1 2
1 3
1 4
3 1 2 2 3
3 2 2 1 3
3 3 3 1 2 4
3 4 4 1 2 3 4
2 2 2 2
11
11
1 1
1 2
2 1 1 2
2 2 1 2
0 0 0 0

Example output

10
-1

Scoring

Each solved input is worth 100 points.