The Jewelry Is Gone

Time Limit: 1 Second    Memory Limit: 32768 KB

Now suppose that a famous thief is in a jewelry store. We assume that the jewelry store is a rectangular room of size n * m (the position of the upper-left corner is (1,1), and that of the lower-right corner is (n,m)). Each grid of the room has a piece of jewel. Every piece of jewel has a certain weight and the thief's package has limit of weight it can hold.

There are some monitoring cameras in the store. Each camera takes one grid (there will be no camera in the original position of the thief), and the camera takes pictures periodically. All the cameras will take their first picture at time 0, and the thief will take action at time 0. If the thief is positioned in some grid while the camera is taking a picture in that grid, the thief will be caught.

Note that every step the thief walk will take one unit of time and the thief can also linger in some grid. When the thief is in some grid, he can pick up the jewel or abandon it immediately.

Now your task is to work out the maximum weight of jewel the thief can take in designated time limit.

Input

The input consists of several test cases.

The first line of each test case contains two integers N and M (1 <= N <= 10, 1 <= M <= 10) which are the column and row sizes of the room. In the following N lines, each line contains M integers denoting the weight of each piece of jewel.

The following line contains an integer K, the number of cameras. Then each of the following K lines contains three integers x, y, and T, where (x, y) is the position of the camera, and T (1 <= T <= 6) is the period of time between two pictures it takes (T = 1 means that the camera will keep taking pictures all the time).

The last line contains four integers X0, Y0, V, L (L <= 7), where (X0, Y0) is the original position of the thief, V is the weight limit of the thief's package, and L is the time limit.

There will be a blank line after each test case.

The input is ended by EOF.

Output

For each test case, output the maximum weight of jewel the thief can take in designated time limit in a line.

Sample Input

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 1
2 1 2
2 2 3
1 1 1000 3

Sample Output

28

Submit

Source: ZOJ Monthly, November 2003