Problem J: Yu-kun Likes a lot of Money

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらいお金が大好きだ。ゆう君は、今日もお金を稼ぐために財宝の眠る島を訪れた。ゆう君は事前に財宝のありかの描かれた地図を手に入れている。その地図をもとに出来るだけ多くのお金を稼ぎたい。ゆう君は最大でどのくらいお金を手に入れることができるだろうか？

Problem

地図、ゆう君の初期位置、財宝の種類とそれらから得られるお金、そして小さい岩を破壊するために必要な費用の情報が与えられる。地図の情報は hマス × wマスのフィールドとして与えられる。地図の各マスに書かれている文字とその意味は次の通りである。

• '@' : ゆう君が最初にいる位置を表す。ゆう君が移動した後は道と同じように扱う。
• '.' : 道を表す。このマスは自由に通ることができ費用もかからない。
• '#' : 大きな岩を表す。このマスは通ることができない。
• '*' : 小さな岩を表す。一定の金額を支払うことで壊すことができる。壊した後は道になる。
• '0','1',...,'9','a','b',...,'z','A','B',...,'Z' : 財宝があるマスを表す。このマスを訪れることでそこに書かれている文字に対応する財宝の金額分のお金を得る。ただしお金を得ることが出来るのは最初に訪れた時のみである。

ゆう君は１回の移動で隣接する上下左右のいずれかのマスに移動することができる。 ただし、地図の外へ出るような移動はできない。

後払いをすることができるため、小さな岩を壊す際にそれに必要な金額をその時に所持している必要はない。そのため、ゆう君は最終的に小さな岩を壊す際にかかった金額の総和以上のお金を得ている必要がある。

ゆう君が得られる最大の金額を出力せよ。

Input

入力は以下の形式で与えられる。

h w n r
c1,1 c1,2 … c1,w
c2,1 c2,2 … c2,w
…
ch,1 ch,2 … ch,w
m1 v1
m2 v2
…
mn vn

１行目に地図の縦の長さh,横の長さw,地図に含まれる財宝の数n,小さな岩を破壊するためにかかる費用rが空白区切りで与えられる。

続くh行に地図を表す各マスの情報c_i,jがw個与えられる。 ( 1 ≤ i ≤ h, 1 ≤ j ≤ w )

続くn行に財宝の種類m_k とその財宝の金額v_kが空白区切りで与えられる。 ( 1 ≤ k ≤ n )

Constraints

入力は以下の制約を満たす。

• 1 ≤ h,w ≤ 8
• 0 ≤ n ≤ min(h×w -1,62) ただし、min(a,b)はa,bの最小値を表す
• 1 ≤ v_i ≤ 10⁵ ( 1 ≤ i ≤ n )
• 1 ≤ r ≤ 10⁵
• c_j,k, m_l を除く全ての入力は整数として与えられる ( 1 ≤ j ≤ h, 1 ≤ k ≤ w, 1 ≤ l ≤ n )
• 地図にはちょうどひとつ'@'が書かれている
• 地図にはちょうどn個の財宝が書かれている
• 地図に書かれている財宝の種類は入力で与えられたm_lのいずれかである
• 地図に同じ種類の財宝が２つ以上現れることはない

Output

ゆう君が得られる最大のお金の金額を1行に出力せよ。

Sample Input1

3 3 1 10
@0.
...
...
0 100

Sample Output1

100

Sample Input2

3 3 1 10
@#b
.#.
.#.
b 100

Sample Output2

0

Sample Input3

3 3 1 20
@*C
..*
...
C 10

Sample Output3

0

---