より良い物を、より安く。今日もどこかのスーパーマーケットで行われるタイムセールでは、激しい闘いが繰り広げられています。ここ会津にある「LL堂」もそんなスーパーマーケットのひとつで、他のチェーン店と対抗すべく、少し変わったタイムセールを実施しています。一般的なタイムセールでは複数の商品が同じ時間に安くなるものですが、LL堂では対象となる商品によって、タイムセールを開始する時間が別々に設定されています。
坂井家はLL堂をよく利用する家庭の一つです。そんな坂井家では、奥様主導のもと、次の日曜に行われるタイムセールに向けて作戦会議を開き、どのような順番で買い物をすれば値引きが最大となるかを分析することになりました。店内を熟知している坂井家は売り場の見取り図を書き、また欲しい品物がどこにあるか、値引きは幾らであるか、売り切れるまでの時間を把握することに成功しました。 ここまでは完璧だった坂井家ですが、分析を行える人がいませんでした。そこで坂井家と親交があったあなたはプログラムを書くことにしました。一人の人が動くことを想定してシミュレーションを行います。
商品は10種類あり、数字1桁の商品番号 g によって 区別されます。タイムセール情報には商品番号 g、 値引き額 d、タイムセールの開始時刻 s と売り切れ時刻 e があります。
店内は横 X、縦 Y のマスで構成される2次元 グリッドで表され、マスごとに通路、商品棚の どちらかが割り当てられています。一つの商品棚には 1種類の商品があり、それは商品番号 g で区別されます。 どの商品を買ってもよいですが、同じ商品番号の商品を複数買ってはいけません。商品棚からは、上下左右に隣接する通路のマスならどんな向きでも商品を取れます。
タイムセールが始まる時刻から商品を取ることができますが、売り切れる時刻からは商品を取ることができません。また、時間は入店した時点で0から始まります。
移動は現在いるマスから上下左右の隣接する通路マスに移動することができますが、商品棚のマスに移動することはできません。グリッドで表される店の外に出ることもできません。１回移動する毎に１単位時間経過します。また、商品を取る時間は考えないものとします。
店内の見取り図と買い物をする人の初期位置と商品のタイムセール情報を入力とし、取ることのできた商品の値引き額の合計の最大値を出力するプログラムを作成してください。
複数のデータセットが与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。
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
1行目に店舗の大きさX, Y (3 ≤ X, Y ≤ 20) が与えられます。続く Y 行に i 列目 j 行目の店内情報 mi,j が以下の内容で与えられます。
. (ピリオド) ：通路のマス
数字 ：商品の番号
P ：買い物をする人の初期位置のマス
続く行にタイムセール情報の数 n (1 ≤ n ≤ 8) が与えられます。続く n 行に i 番目のタイムセール情報 gi di si ei が与えられます(0 ≤ gi ≤ 9, 1 ≤ di ≤ 10000, 0 ≤ si, ei ≤ 100)。
データセットの数は 50 を超えません。
データセットごとに、取ることのできる商品の値引き額合計の最大値を１行に出力します。
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