4083：Three Kingdom Chess

Zhuge Liang and Zhou Yu were famous strategists in The Three Kingdoms Period.
During The War of the Red Cliff in which Cao Chao was defeated, they often sat together to play chess. But the chess they played was special.
We can call the chess "Three Kingdom Chess". There are 2 players, and each one has some soldiers. All the soldiers are put on an N × M chessboard. Each grid on the chess board can be mountain, plain or lake. And there are 3 kinds of soldiers which are footman, archer and rider. All kind of soldiers can stay at or pass through plains. None of them can stay at or pass through lakes. Only footmen and archers can stay at or pass through mountains.
There are at most K turns in the game. Two players take turns to act. The first turn is Zhuge Liang's turn, the second turn is Zhou Yu's, the third turn is Zhuge Liang's…and so on. When one player's soldiers are all destroyed or after the Kth turn, the game ends. In each turn, the player can move one of his soldiers to a destination and then let it attack one of the opponent's soldiers.
The rule of moving is as below. Every kind of soldiers has its "pace length". A soldier with "pace length" of q can move at most q steps(you can also let your soldier move 0 step). On each step, a soldier can move up, down, left or right by one grid. But please note that no soldier can pass a lake and a rider can't pass a mountain, as mentioned above. A soldier is also not able to pass a grid which is occupied by an enemy soldier. A soldier can pass, but cannot stay at a grid which is occupied by his comrade.
After a soldier reaching his moving destination, he can launch an attack. A soldier can attack an enemy soldier who is in his "attack region". The attack regions of different kinds of soldiers are shown in the figures below:



It means that the soldier in the grid with a circle can attack one enemy soldier who is in the black grids.
Every soldier has a "strength" property. A soldier's strength will decrease if he is attacked. The strength decrement equals to S × F, which S is the attacker's strength, and F is the attacking factor. The attacking factor is 2 when a footman attacks an archer, an archer attacks a rider and a rider attacks a footman. It's 1 when a footman attacks a footman, a rider 6 attacks a rider and an archer attacks an archer. It's 0.5 when a footman attacks a rider, a rider attacks an archer and an archer attacks a footman.
A soldier will be destroyed and disappear if its strengths is equal to or less than 0.
In one turn, a soldier can only launch one attack, and he can't move again in the same turn after attacking.
At the end, the score you get is the sum of strength of all your soldiers minus the sum of strengths of all your opponent's soldiers. So the score can be negative. Suppose Zhuge Liang and Zhou Yu were both very clever and always chose the best strategy to get as many score as possible, so what's the maximum score could Zhuge Liang get in the game?

There are several test cases. For each test case:
The first line contains 3 integers, N, M (1 <= N, M <= 5) and K (1 <= K <= 10), indicating that the chessboard is N × M, and the game will end after K turns.
Then N lines follow, each containing M integers. Every integer represents a grid, showing the grid's property. 0 stands for plain, 1 stands for mountain and 2 stands for lake.
The next line contains 4 integers, T (1 <= T <= 6), S1, S2 and S3, indicating that there are T soldiers on the chessboard at the beginning. It is guaranteed that no more than one soldier stay at the same grid. S1, S2 and S3 mean the "pace length" of footman, rider and archer.
For the next T lines, each line contains 5 integers x, y, a, b and c, describing a soldier.
The soldier is in row x and column y (The coordinates x, y start from 1). If a=0 then the soldier is Zhuge Liang's and if a=1 then it is Zhouyu's. The strength of the soldier is b. c=0 means the soldier is a footman, c=1 means it is a rider and c=2 means it is an archer.
The input ends with N = M = K = 0.

For each test case, output one line containing the maximumscore Zhuge Liang can get in the game.