問題
あるところにH学校に通う、Oちゃんがいました。
H学校では明日遠足があります。
遠足にはお菓子を持って行っていいらしいので、Oちゃんはお母さんにC円(0≦C≦1000)のお小遣いをもらい、お菓子を買いに行くことにしました。
Oちゃんの住むJ商店街は、縦がH(1≦H≦100)、横がW(1≦W≦100)の広さがあり、N個(0≦N≦500)のお菓子屋さんがあります。
専門店がそろっているため、全てのお菓子屋さんで、売っているお菓子は1種類だけです。
また、Oちゃんにはお菓子の好みがあり、お菓子それぞれに対してOちゃんの満足度Xi(1≦Xi≦100)とお菓子の値段Yi(1≦Yi≦100)が決められています。
Oちゃんは余ったお小遣いは貯金しようと考え、コストパフォーマンスの高いお菓子を優先的に選び、残金を貯金することにしました。
買うお菓子が決まったら、Oちゃんは自分の好きなお菓子(満足度の高いお菓子)から順に買いに行きます。
Oちゃんは小さいので縦横にしか移動できません。
Oちゃんが1マス移動する毎に1分経過します。
お店がある場所を通過することはできません。
Oちゃんがお菓子屋さんの存在する座標に移動したときお菓子を買ったものとします。
お菓子を買うことでの時間経過は発生しません。
Oちゃんの家は商店街の(0,0)の位置に存在します。
J商店街内の'1'の場所にはお菓子屋さん1が存在します。
お菓子屋さん1で販売しているお菓子の満足度をX1、値段をY1とします。
Oちゃんは飽き性のため同じお菓子を複数買うことはしません。
お菓子のコストパフォーマンスが等しいときには安いものを選ぶことにする。
Oちゃんが家を出て、お菓子を買い、再び家に帰ってくるまでにどれだけの時間が経過するか求めてください。
入力
H W C c1,1 c1,2 c1,3……c1,W c2,1 c2,2 c2,3……c2,W c3,1 c3,2 c3,3……c3,W ... ... cH,1 cH,2 cH,3……cH,W N X1 Y1 X2 Y2 X3 Y3 ... ... XN YN
1行目にはH,W,Cが空白区切りに与えられる。
続くH行ではci,jが空白区切りにW文字与えられる。
ci,jは0～Nの数字からなる。
H+2行目にはNが与えられる。
続くN行ではXi,Yiが空白区切りで与えられる。
出力
Oちゃんが家を出て、お菓子を買い、再び家に帰ってくるまでの経過時間を1行で出力する。
入出力例
入力例
6 4 300 0 0 6 0 0 0 2 0 0 0 0 1 3 0 4 0 0 0 0 0 0 5 0 0 6 3 70 7 130 5 100 2 50 6 110 4 80
出力例
16
