Time Sale

Better things, cheaper. There is a fierce battle at the time sale held in some supermarkets today. "LL-do" here in Aizu is one such supermarket, and we are holding a slightly unusual time sale to compete with other chain stores. In a general time sale, multiple products are cheaper at the same time, but at LL-do, the time to start the time sale is set differently depending on the target product.

The Sakai family is one of the households that often use LL-do. Under the leadership of his wife, the Sakai family will hold a strategy meeting for the time sale to be held next Sunday, and analyze in what order the shopping will maximize the discount. .. The Sakai family, who are familiar with the inside of the store, drew a floor plan of the sales floor and succeeded in grasping where the desired items are, how much the discount is, and the time until they are sold out. The Sakai family was perfect so far, but no one could analyze it. So you got to know the Sakai family and decided to write a program. The simulation is performed assuming that one person moves.

There are 10 types of products, which are distinguished by the single-digit product number g. The time sale information includes the item number g, the discount amount d, the start time s of the time sale, and the sold-out time e.

The inside of the store is represented by a two-dimensional grid consisting of squares X in width and Y in height, and either a passage or a product shelf is assigned to each square. There is one type of product on a shelf, which is distinguished by item number g. You can buy any item, but you must not buy more than one item with the same item number. From the product shelves, you can pick up products in any direction as long as they are in the aisle squares that are adjacent to each other.

You can pick up items from the time when the time sale starts, but you cannot pick up items from the time when they are sold out. Also, the time starts from 0 when you enter the store.

You can move from the current square to the adjacent aisle squares on the top, bottom, left, and right, but you cannot move to the squares on the product shelves. You can't even go outside the store represented by the grid. One unit time elapses for each move. Also, do not consider the time to pick up the product.

Please create a program that outputs the maximum value of the total discount amount of the products that you could get by inputting the floor plan of the store, the initial position of the shopper and the time sale information of the product.

input

Given multiple datasets. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:

X Y m1,1 m2,1 ... mX,1 m1,2 m2,2 ... mX,2 :: m1, Y m2, Y ... mX, Y n g1 d1 s1 e1 g2 d2 s2 e2 :: gn dn sn en

The first line gives the store sizes X, Y (3 ≤ X, Y ≤ 20). In the following Y row, the store information mi, j in the i-th column and j-th row is given with the following contents. . (Period): Aisle square Number: Product number P: The initial position of the shopper

The following line is given the number of timesale information n (1 ≤ n ≤ 8). The next n lines are given the i-th time sale information gi di si ei (0 ≤ gi ≤ 9, 1 ≤ di ≤ 10000, 0 ≤ si, ei ≤ 100).

The number of datasets does not exceed 50.

output

For each data set, the maximum value of the total discount amount of the products that can be taken is output on one line.

Example

Input

6 5 1 1 . 0 0 4 1 . . . . . . . 2 2 . . . . 2 2 3 3 P . . . . . 5 0 50 5 10 1 20 0 10 2 10 5 15 3 150 3 5 4 100 8 9 0 0

Output

180

inputFormat

outputFormat

outputs the maximum value of the total discount amount of the products that you could get by inputting the floor plan of the store, the initial position of the shopper and the time sale information of the product.

input

Given multiple datasets. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:

X Y m1,1 m2,1 ... mX,1 m1,2 m2,2 ... mX,2 :: m1, Y m2, Y ... mX, Y n g1 d1 s1 e1 g2 d2 s2 e2 :: gn dn sn en

The first line gives the store sizes X, Y (3 ≤ X, Y ≤ 20). In the following Y row, the store information mi, j in the i-th column and j-th row is given with the following contents. . (Period): Aisle square Number: Product number P: The initial position of the shopper

The following line is given the number of timesale information n (1 ≤ n ≤ 8). The next n lines are given the i-th time sale information gi di si ei (0 ≤ gi ≤ 9, 1 ≤ di ≤ 10000, 0 ≤ si, ei ≤ 100).

The number of datasets does not exceed 50.

output

For each data set, the maximum value of the total discount amount of the products that can be taken is output on one line.

Example

Input

6 5 1 1 . 0 0 4 1 . . . . . . . 2 2 . . . . 2 2 3 3 P . . . . . 5 0 50 5 10 1 20 0 10 2 10 5 15 3 150 3 5 4 100 8 9 0 0

Output

180

样例

6 5
1 1 . 0 0 4
1 . . . . .
. . 2 2 . .
. . 2 2 3 3
P . . . . .
5
0 50 5 10
1 20 0 10
2 10 5 15
3 150 3 5
4 100 8 9
0 0

180