Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
127 - ZOJ Monthly, June 2013 - G
Sid Meier's Civilization

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.

```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
```

```1
1
```

#### Hint

In sample 1, you have just 1 land at the beginning which is your capital city at (3,2). So you can just arrange your first worker working on this land. Since the land's production value V is 1, you can get 1 stone at turn 0. Then at the beginning of Turn 1, you already have enough stone to build the Great Wall, so the answer is 1 Turn.

In sample 2, although you have 2 lands, both of them cannot produce any stones. So you can just get stones by finding ancient ruins. Remember that at Turn 0 the scout is at your capital city which is at (3,1). So the ruin at (5,1) is the nearest. At turn 0, you can let your scout go down 2 steps, and you will find the ruin and get 2 stones immediately. Then at the beginning of Turn 1, you already have 2 stones which are enough to build the Great Wall, so the answer is also 1 Turn.

Author: HUANG, Qiao
Submit    Status