0422 - 旅行代理店

時間制限 1 秒 / メモリ制限 256 MB / 得点 5 / Writer ei1417 / x 3 / 統計 /

    タグ:
TLE
1sec
MLE
256MB
得点
5

問題

ここはS県H市、H市にはN個の観光スポットがあり、それぞれ１からNまでの番号が割り振られています。
番号が隣り合う観光スポットの間に道が作られていて、そこを移動することで隣り合う番号の観光スポットに移動できます。
観光スポットを見るのにお金はいりませんが、道を移動する際にお金がかかります。
かかるお金はその道の距離×移動した日の基本料金です。
基本料金のデータは１日目からS日目までのデータがあります。

観光スポットの中で番号が１番の観光スポットは旅行代理店です。
板本くんはその旅行代理店に勤めています。お客さんにより安価なプランを提案するのが板本君の仕事です。
お客さんは次のような旅行プランを希望します。
まず前日（０日目）に１番の観光スポットから２番の観光スポットまで移動します。このとき、２番までに移動するためにかかる料金は１番目の観光スポットと２番目の観光スポットの間の道の距離×１です。
１日目は２番の観光スポットを見ます。
その後隣り合う番号の観光スポットのどちらか(今回で言うと１番か３番)に移動し、２日目はその観光スポットを見ます。
二日連続で同じ番号の観光スポットを見ることは出来ません。
隣り合う観光スポットに１回移動する間に日付が１進みます。(1日目に出発した場合次の観光スポットにつくのは２日目の時）
これを最終日まで繰り返し、最終日にg番の観光スポットを見るようなプランです。最終日にg番から家に帰る料金はかかりません。
もしこの条件を満たすプランが複数有る場合、より安く移動できるプランを選びます。

板本君の勤める旅行代理店にはM個の料金設定があります。
この料金設定は旅行に実際にかかる費用と旅行代理店の利益の２つを兼ねています。
たとえば4500円で移動できる旅行プランがあり、料金設定が1000円、5000円、10000円の３種類あったとします。
1000円の料金設定だと、旅行にかかる費用4500円がまかなえません。
10000円と5000円の料金設定だと、4500円はまかなえますが、5000円の方が安いためお客は旅行代理店に5000円支払います。
この5000円から旅行にかかる費用4500円を引いた値500円が今回の旅行代理店の利益になります。

今日はQ人のお客が旅行代理店に来ました。この日の旅行代理店の利益は合計いくらになったか調べてください。

入力

N S M Q
l1
l2
.
.
.
lN-1
c1
c1
.
.
.
cS
p1
p2
.
.
.
pM
d1 g1
d2 g2
.
.
.
dQ gQ

１行目に観光スポットの数N,基本料金のデータの数S,料金設定の数M,客の数Qが空白区切りで与えられる。
２行目からN-1行にわたって観光スポットと観光スポットの間の道の距離が与えられる。i(1≦i≦N)行目には観光スポットiと観光スポットi+1の間の道の距離が与えられる。
N行目からS行にわたって基本料金のデータが与えられる。i(1≦i≦S)行目にはi日目の基本料金が与えられる。
N+S行目からM行にわたって料金設定のデータが与えられる。
N+S+M行目からQ行にわたって客の要望が与えられる。i(1≦i≦Q)行目にはi番目に来た客がdi日かけて最終的にgiを見ることを希望していることを示す。

出力

お店が得た利益の合計を出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • 2≦N≦1000
  • 1≦M≦1000
  • 1≦S≦1000
  • 1≦Q≦1000
  • 1≦li≦1000
  • 0≦ci≦1000
  • 1≦pi≦10000000
  • 1≦di≦S+1
  • 1≦gi≦N

入出力例

入力例1

5 5 3 3
2
5
9
3
3
5
6
1
2
10
30
50
2 3
4 3
3 1

出力例1

15

解説

観光スポット１から観光スポット２までの距離が2、２から３が5、３から４が9、４から５が3である。
１日目の基本料金が3、２日目が5、３日目が6、４日目が1、５日目が2である。
料金設定は10円、30円、50円の３種類である。
一人目のお客は2日で最後に観光スポット3にいるプランを希望した。
まず観光スポット1から観光スポット2に移動し、１日目に観光スポット2を見た後観光スポット3に行くプランしかこの条件を達成するプランは存在しないため、このプランにする。
このときかかる費用は2+15で17円である。よって、料金設定は30円が適用され、30-17=13で13円の利益となる。
二人目のお客は1→2→1→2→3のプランと1→2→3→2→3のプランと1→2→3→4→3の３種類のプランがある。
1つめのプランは2+6+10+30で48円,二つめのプランは2+15+25+30で72円,三つ目のプランは2+15+45+54で116円かかる。
最も安い１つめのプランを採用し、50円の料金設定を適用、利益は50-48=2で2円の利益となる。
三人目のお客の希望するプランは存在しないため利益は発生しない。
よって、この日の利益は13+2+0となり、15円となる。

入力例2

3 3 3 1
100
100
100
100
100
1
10
100  
3 2

出力例2

0

解説

料金設定によっては条件を満たすプランがあってもお金が支払われず利益がないことに注意せよ。

入力例3

10 8 9 3
5
1
4
6
8
5
3
5
7
8
1
3
2
5
7
11
3
10
30
50
75
100
125
150
200
500
8 7
7 6
9 10

出力例3

61