Time Sale

Time Limit : 5 sec, Memory Limit : 65536 KB

タイムセール

より良い物を、より安く。今日もどこかのスーパーマーケットで行われるタイムセールでは、激しい闘いが繰り広げられています。ここ会津にある「LL堂」もそんなスーパーマーケットのひとつで、他の全国チェーン店と対抗すべく、少し変わったタイムセールを実施しています。一般的なタイムセールでは複数の商品が同じ時間に安くなるものですが、LL堂では対象となる商品によって、タイムセールを開始する時間が別々に設定されています。

坂井家はLL堂をよく利用する家庭の一つです。そんな坂井家では、奥様主導のもと、次の日曜に行われるタイムセールに向けて作戦会議を開き、どのような順番で買い物をすれば値引きが最大となるかを分析することになりました。店内を熟知している坂井家は売り場の見取り図を書き、また欲しい品物がどこにあるか、値引きは幾らであるか、売り切れるまでの時間を把握することに成功しました。 ここまでは完璧だった坂井家ですが、分析を行える人がいませんでした。そこで坂井家と親交があったあなたはプログラムを書くことにしました。一人の人が動くことを想定してシミュレーションを行います。

商品は10種類あり、数字1桁の商品番号gによって 区別されます。タイムセール情報には商品番号g、 値引き額d、タイムセールの開始時刻sと売り切れ 時刻eがあります。

店内は横x、縦yのマスで構成される2次元 グリッドで表され、マスごとに通路、商品棚の どちらかが割り当てられています。一つの商品棚には 1種類の商品があり、それは商品番号gで区別されます。 どの商品を買ってもよいですが、同じ商品番号の商品を複数買ってはいけません。商品棚からは、上下左右に隣接する通路のマスならどんな向きでも商品を取れます。

タイムセールが始まる時刻から商品を取ることができますが、売り切れる時刻からは商品を取ることができません。また、時間は入店した時点で0から始まります。

移動は現在いるマスから上下左右の隣接する通路マスに移動することができますが、商品棚のマスに移動することはできません。グリッドで表される店の外に出ることもできません。1回移動する毎に1単位時間経過します。また、商品を取る時間は考えないものとします。

店内の見取り図と買い物をする人の初期位置と商品のタイムセール情報を入力とし、取ることのできた商品の値引き額の合計の最大値を出力するプログラムを作成してください。ただし、店舗の大きさx, yは3以上20以下、タイムセール情報の数nは1以上8以下、タイムセールが始まる時刻s、商品が売り切れる時刻eはともに0以上100以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の通りです。

1行目 店舗の大きさ x y(整数 整数;半角空白区切り)
2行目 1行目の店内情報 m1 m2 … mx(すべて半角文字;半角空白区切り)
    各記号の値と意味は次の通りです。
    . (ピリオド) :通路のマス
    数字 :商品の番号
    P :買い物をする人の初期位置のマス
3行目 2行目の店内情報

y+1行目 y行目の店内情報
y+2行目 タイムセール情報の数 n(整数)
y+3行目 第1のタイムセール情報 g d s e(すべて整数;半角空白区切り)
y+4行目 第2のタイムセール情報

y+n+2行目 第nのタイムセール情報

出力

入力データセットごとに、取ることのできる商品の値引き額合計の最大値を出力します。

入力例

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

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/