Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
103 - ZOJ Monthly, February 2011 - J
The Great Wall II

Time Limit: 10 Seconds      Memory Limit: 65536 KB

Long long ago, in the forgotten land, there is a rich country named X. There were several countries in the forgotten land and some of them were so aggressive that they often invade other countries, including X. X was so rich but its army was not strong enough to beat these invaders totally. So, the king of country X decided to build a national defense system to prevent the attack from other countries. The main part of the system is the great wall!

As far as the king knew, the map of the forgotten land is a rectangle with n * m grids, and each country occupied a single grid.

Some allied countries nearby want to join the system and were willing to pay some money for it to prevent themselves from the attack from those aggressive countries.

Now, knowing how much money each country was willing to pay and the cost to build wall at each board, the king must decide which countris are accepted to make the total cost at low at possible.

If a country has been accepted to join in the defense system, it will be safe when the great wall is done. Safe means that it's impossible to invade the country without destroying some part of the great wall from those aggressive countries (maybe some unknown country from the outside of the map). But those countries don't want to be isolated.So there must be a way to go from country X to any other countries in the defense system without crossing the great wall.

For example, in the above map, X means country X, E means the aggressive country and A means the allied country. The cost to build great wall along each border is 1 million doller. If the allied country afford more than 6 million doller, the best way is to build the great wall along the bule curve. Note that it's possible to build two parallel great wall along a single border, and the cost of each great wall is still 1 million doller.

Input

There are about 30 cases.

  • The first line of each cases were two integer numbers N, M (1 <= N, M <= 10).
  • Then 2 * N + 1 lines followed, the jth integer of the (2 * i)th line is the cost to build great wall on the border between gird(i - 1, j) and grid(i, j) while the jth integer of the (2 * i + 1)th line is the cost (0 < cost <= 10000)of building great wall on the border between gird(i, j - 1) and grid(i, j).
  • The 2 * N + 2th line contains a single integer K(1 <= K <= 6)
  • The K lines followed, each line contains three integers afford, i, j (-1 <= afford <= 10000, 0 <= i < N, 0 <= j < M), means the country in the grid(i, j) want to pay X afford money to the great wall. A negative afford means that the country is aggressive. A zero afford means the country is X.
  • There will be one a only one country with zero afford in each case.

Output

A single integer, the minimum cost. Note that the cost can be negative when country X can earn money from the building of the great wall.

Sample Input

1 3
1 1 1
1 1 1 1
1 1 1
3
0 0 0
-1 0 1
3 0 2

2 2
1 1 
1 1 1 
1 1 
1 1 1 
1 1 
4
0 0 0
-1 0 1
-1 1 0
5 1 1

3 3
1 1 1
1 1 10 1
10 1 10
1 1 1 1
10 1 10
1 10 10 1
1 1 1
3
0 0 0
-1 1 1
2 2 2

Sample Output

4
3
13

Hint

In the second sample, we can build the great wall along the blue curve. Note that country X and A are reachable from each other.
Author: WANG, Yelei
Contest: ZOJ Monthly, February 2011
Submit    Status