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:
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

const static int tx[4] = {+0,+1,+0,-1};
const static int ty[4] = {-1,+0,+1,+0};

bool dp[21][21][101][1<<10];

class State{
public:
  int x;
  int y;
  int time;
  int got;
  bool operator<(const State& s) const {
    return time < s.time;
  }
  bool operator>(const State& s) const {
    return time > s.time;
  }
  State(int x,int y,int time,int got) 
    : x(x), y(y), time(time), got(got){}
};

class Goods{
public:
  int item_id;
  int discounted_price;
  int sale_start_time;
  int sale_end_time;
  Goods(int item_id,int discounted_price, int sale_start_time,int sale_end_time)
    : item_id(item_id),discounted_price(discounted_price),sale_start_time(sale_start_time), sale_end_time(sale_end_time){}
  Goods(){}
};

int main(){
  int W,H;
  while(~scanf("%d %d",&W,&H)){
    if(W == 0 && H == 0) break;
    char stage[21][21];
    memset(dp,false,sizeof(dp));
    int sx,sy;
    for(int y = 0; y < H; y++){
      for(int x = 0; x < W; x++){
        char cell[8];
        scanf("%s",cell);
        stage[y][x] = cell[0];
        if(stage[y][x] == 'P'){
          sy = y;
          sx = x;
        }
      }
    }
    int total_time_sales;
    scanf("%d",&total_time_sales);

    map<int,Goods> goods;
    for(int i = 0; i < total_time_sales; i++){
      int item_id;
      int discounted_price;
      int sale_start_time;
      int sale_end_time;
      scanf("%d %d %d %d",
            &item_id,
            &discounted_price,
            &sale_start_time,
            &sale_end_time);
      goods[item_id] = Goods(item_id,discounted_price,sale_start_time,sale_end_time);
    }
    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(sx,sy,0,0));
    dp[sx][sy][0][0] = true;
    while(!que.empty()){
      State s = que.top();
      que.pop();
      for(int i = 0; i < 4; i++){
        int dx = s.x + tx[i];
        int dy = s.y + ty[i];
        if(dx < 0 || dx >= W || dy < 0 || dy >= H) continue;
        if(stage[dy][dx] == '.' || stage[dy][dx] == 'P') continue;
        const Goods& g = goods[stage[dy][dx] - '0'];
        if(g.sale_start_time <= s.time && s.time < g.sale_end_time){
          s.got |= (1 << g.item_id);
        }
      }

      for(int i = 0; i < 4; i++){
        int dx = s.x + tx[i];
        int dy = s.y + ty[i];
        if(dx < 0 || dx >= W || dy < 0 || dy >= H) continue;
        if(stage[dy][dx] != '.' && stage[dy][dx] != 'P') continue;
        if(dp[dx][dy][s.time+1][s.got]) continue;
        if(s.time+1 > 100) continue;
        dp[dx][dy][s.time+1][s.got] = true;
        que.push(State(dx,dy,s.time+1,s.got));
      }
    }

    int res = 0;
    for(int y = 0; y < H; y++){
      for(int x = 0; x < W; x++){
        for(int time = 0; time <= 100; time++){
          for(int S = 0; S < (1<<10); S++){
            if(dp[x][y][time][S]){
              int sum = 0;
              for(int i = 0; i < 10; i++){
                if(S & (1<<i)){
                  sum += goods[i].discounted_price;
                }
              }
              res = max(res,sum);
            }
          }
        }
      }
    }
    printf("%d\n",res);
  }
}