Sid Meier's Civilization is a famous turn-based strategy game. This problem is inspired by this great game. But some rules in this problem are different from the real game. If you have played the game before, you'd better read the description more carefully.
At the beginning (Turn 0) of the game, all civilizations will be born on a big map. The map can be described as m*n lands. Some lands will belong to your civilization (such as China) at the beginning. Of course there are some other lands that belong to other civilizations too.
Every 5 turns (Such as Turn 5, Turn 10 and etc.), all the lands which is adjacent to your territory will also become your new territory. But notice that if a land already belongs to another civilization, it will remain belonging to that civilization.
Now you want to build the Great Wall which will be a wonder of the world. Building The Great wall needs a lot of resources, such as stones. At the beginning, you don't have any stones. In every turn, you can get some stones while the number of stones you get depends on the condition of your territory lands and how you arrange your people to work. Every land can produce stones as long as there is a worker working on it.
At the beginning (Turn 0) you have 1 worker, then every 5 turns you will get a new worker. Once you have a worker, you must arrange him to work on a land immediately. For example, you have a worker at Turn 0, so you must give this worker a land at Turn 0, and he will work and live on that land forever. One land can only accept one worker. If you have no land available for the new worker, he will not work for you anymore.
Different lands may have different production. We use an integer number V to describe a land's production, and if there is a worker working on it, then every turn the number V will reduce 1. For example: At Turn 5, you got a new worker working on a land whose production V is 3. So you can get 3 stones from this land at Turn 5, then 2 stones at Turn 6, and 1 stones at Turn 7. Finally you won't get any stones from this land after Turn 7.
Besides, there are some ancient ruins on the whole map. If you find a ruin, you can get some number of stones directly. At Turn 0, you have a scout in your capital. During 1 Turn, the scout can move at most 2 steps. In every step, he can move to one of the four neighboring lands (up, down, left, right). If he walks into a land containing ancient ruin, then you can get the stones immediately. But notice that the scout cannot move out of the map or move into the land belonging to other civilizations. No two ruins are in the same land and your capital city does not contain ancient ruin.
Now given the information of the map and the cost of the Great Wall, can you find the minimum Turns we need to build the Great Wall?
Input
The first line contains 2 integer numbers m ( 1 <= m <= 50 ) and n ( 1 <= n <= 50 ) indicating the size of the map and another integer number C ( 1 <= C <= 10000 ) indicating the stones needed to build the Great Wall.
The next m line each contains n characters. '*' means this land belongs to you at the beginning. 'X' means this land belongs to other civilization at the beginning. '.' means this land does not belong to any civilization at the beginning.
Then there are another m lines each containing n integer numbers separated by a space which indicates the production number V ( 0 <= V <= 50 ) of each land.
The following line contains 1 integer number K ( 0 <= K <= 5 ) which is the number of ancient ruins on the whole map.
Then K lines follow, each containing 2 integer numbers x ( 1 <= x <= m ) and y ( 1 <= y <= n ) indicating the position of the ancient ruin and another integer S ( 1 <= S <= 50 ) which is the number of stones you can get if you find this ruin.
Finally there is a line containing 2 integer numbers X ( 1 <= X <= m ) and Y ( 1 <= Y <= n ) indicating the position of your capital city.
Output
For each case, output 1 integer which is the minimum Turns we need to build the Great Wall.
If there is no solution, output -1 instead.
Sample Input
5 5 1
X...X
.....
.*...
.....
X...X
1 0 0 0 1
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 1
0
3 2
5 5 2
X...X
.....
**...
.....
.....
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2
5 1 2
3 4 2
3 1
Sample Output
1
1
