Problem: 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

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Cell{
	Cell(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	bool operator<(const struct Cell &arg) const{
		if(row != arg.row){
			return row < arg.row;
		}else{
			return col < arg.col;
		}
	};
	int row,col;
};

struct Info{
	int discount,start,end;
};

struct Data{
	Data(int arg_row,int arg_col,int arg_total_dist){
		row = arg_row;
		col = arg_col;
		total_dist = arg_total_dist;
	}

	int row,col,total_dist;
};

struct SALE{
	SALE(){
		state = time = row = col = sum_discount = 0;
	}

	SALE(int arg_state,int arg_time,int arg_row,int arg_col,int arg_sum_discount){
		state = arg_state;
		time = arg_time;
		row = arg_row;
		col = arg_col;
		sum_discount = arg_sum_discount;
	}

	int state,time,row,col,sum_discount;
};

int W,H;
int POW[11];
int dp[1024][20][20];
Info info[10];
bool is_sale[10];
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};

char base_map[20][21];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}



void func(){

	char buf[2];

	int start_row,start_col;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			scanf("%s",buf);
			base_map[row][col] = buf[0];
			if(buf[0] == 'P'){
				base_map[row][col] = '.';
				start_row = row;
				start_col = col;
			}
		}
	}

	int N;
	scanf("%d",&N);

	int g,d,s,e;

	for(int i = 0; i < 10; i++)is_sale[i] = false;

	for(int loop = 0; loop < N; loop++){
		scanf("%d %d %d %d",&g,&d,&s,&e);

		info[g].discount = d;
		info[g].start = s;
		info[g].end = e;

		is_sale[g] = true;
	}

	int limit = POW[10];

	for(int state = 0; state < limit; state++){
		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				//dp[state][row][col] = BIG_NUM; //????????????????????????
				dp[state][row][col] = -1;
			}
		}
	}

	queue<SALE> Q;

	dp[0][start_row][start_col] = 0;

	SALE first;
	first.row = start_row;
	first.col = start_col;
	first.state = 0;
	first.sum_discount = 0;
	first.time = 0;

	Q.push(first);
	int max_value = 0;

	while(!Q.empty()){

		//printf("row:%d col:%d time:%d sum:%d state:%d\n",Q.front().row,Q.front().col,Q.front().time,Q.front().sum_discount,Q.front().state);

		max_value = max(max_value,Q.front().sum_discount);

		for(int i = 0; i < 4; i++){
			int adj_row = Q.front().row + diff_row[i];
			int adj_col = Q.front().col + diff_col[i];

			if(rangeCheck(adj_row,adj_col) == false)continue;

			if(base_map[adj_row][adj_col] == '.'){ //???????????´???

				if(dp[Q.front().state][adj_row][adj_col] < Q.front().sum_discount){
					dp[Q.front().state][adj_row][adj_col] = Q.front().sum_discount;

					SALE next_sale;
					next_sale.row = adj_row;
					next_sale.col = adj_col;
					next_sale.state = Q.front().state;
					next_sale.sum_discount = Q.front().sum_discount;
					next_sale.time = Q.front().time+1;

					//printf("?????? row:%d col:%d?????????%d state:%d??§????§?\n",adj_row,adj_col,Q.front().time+1,Q.front().state);

					Q.push(next_sale);
				}
			}else if(base_map[adj_row][adj_col] >= '0' && base_map[adj_row][adj_col] <= '9'){

				int adj_item = base_map[adj_row][adj_col]-'0';

				if(Q.front().state & (1 << adj_item))continue;
				if(is_sale[adj_item] == false)continue;

				int next_state = Q.front().state + POW[adj_item];

				if(Q.front().time >= info[adj_item].start && Q.front().time < info[adj_item].end){ //??????????§??????????????????§?????????????????????

					if(dp[next_state][Q.front().row][Q.front().col] < Q.front().sum_discount+info[adj_item].discount){

						dp[next_state][Q.front().row][Q.front().col] = Q.front().sum_discount+info[adj_item].discount;

						SALE next_sale;
						next_sale.row = Q.front().row;
						next_sale.col = Q.front().col;
						next_sale.state = next_state;
						next_sale.sum_discount = Q.front().sum_discount+info[adj_item].discount;
						next_sale.time = Q.front().time;

						//printf("?????? row:%d col:%d?????????%d state:%d??§????§?\n",adj_row,adj_col,Q.front().time+1,Q.front().state);

						Q.push(next_sale);

					}

				}else if(Q.front().time < info[adj_item].start){

					/*if(dp[next_state][Q.front().row][Q.front().col] < Q.front().sum_discount+info[adj_item].discount){

						dp[next_state][Q.front().row][Q.front().col] = Q.front().sum_discount+info[adj_item].discount;*/
						SALE next_sale;
						next_sale.row = Q.front().row;
						next_sale.col = Q.front().col;
						next_sale.state = Q.front().state;
						next_sale.sum_discount = Q.front().sum_discount;
						next_sale.time = info[adj_item].start;

						//printf("?????\?????? row:%d col:%d?????????%d state:%d??§????§?\n",adj_row,adj_col,Q.front().time+1,Q.front().state);

						Q.push(next_sale);
					//}
				}
			}
		}
		Q.pop();
	}

	printf("%d\n",max_value);
}


int main(){

	for(int i = 0; i <= 10; i++)POW[i] = pow(2,i);

	while(true){
		scanf("%d %d",&W,&H);
		if(W == 0 && H == 0)break;

		func();
	}

	return 0;
}