Problem D
めったに会えない

ルナと弟のソロモンは、お互いに非常に遠くに住んでいます。 ルナはソロモンに会いに行く日を予定に入れています。 ルナがソロモンのところに行くための唯一の方法は、電車に乗ることです。 ソロモンはかなり暑がりなので、ルナは彼の家に泊まることはなく、その日のうちに帰ります。 ルナは夜勤の仕事をしているので、それが一番いいのかもしれません。

電車に乗るにはもちろんお金がかかります。電車に乗ることは自然の法則ではありません! 電車には様々なタイプのチケットがあり、それぞれのチケットには有効期限と価格があります（例えば、1ヶ月券¹があるかもしれません）。 有効期限の長いチケットは、有効期限の短いチケットよりも必ず値段が高くなります。 通常、ルナはWHMarsで買い物をしますが、仕事のために移動することもあり、代わりに何もかもがWHMarsの半額であるSevenus Elevenusに行くこともあります。

ルナは、$N$日の異なる日、$d_1、\cdots 、d_N$にソロモンを訪れます。 チケットには$M$個の異なる種類があり、$i$番目のチケットは$g_i$日間有効で、$p_i$の費用がかかります。 ここで、$p_i$は、WHMarsでのチケットの値段です。 チケットの有効期限は日単位で計算され、正確に$g_i$日間有効です。 つまり、チケット$i$が$d$日目に購入された場合、$d,d+1,\dots ,d+g_i-1$日目に有効ということになります。 ソロモンへの訪問と同じ日に仕事があった場合、ルナはSevenusで安くチケットを購入して、その日に使うことができます。 購入したチケットはすぐに有効になり、有効化を遅らせることはできません。

ルナがソロモンのところに行くためのチケットをすべて購入するための最小の価格がいくらかを彼女に教えてあげてください。

入力

入力には5行が含まれています。 1行目には3つの整数が含まれています。

• ルナがソロモンを訪れる回数$N$ ($1\le N\le {10}^5$)

• チケットの種類数$M$ ($1\le M\le 10$)

• ルナが仕事に行く回数$K$ ($0\le K\le {10}^5$).

2行目には$N$個の整数$d_i$ ($1\le d_i\le 5\cdot {10}^5$)が含まれています。これは、ルナがソロモンを訪れる日を表します。

3行目には$M$個の整数$g_i$ ($1\le g_i\le 5\cdot {10}^5$)が含まれています。これは、それぞれのチケットの有効期限の日数です。

4行目には$M$個の整数$p_i$ ($2\le p_i\le {10}^4$)が含まれています。これは、それぞれのチケットのWHMarsでの価格です。$p_i$はつねに偶数です。

5行目は最終行で、$K$個の整数$r_i$ ($1\le r_i\le 5\cdot {10}^5$)が含まれています。これは、ルナが仕事に行く日、したがって、チケットを半額で購入できる日です。

2～5行目の値は狭義の単調増加となっています。

出力

出力は単一の整数で、ルナがソロモンを訪問するために支払う最小の金額です。

ルナが仕事に行くためのチケットを購入する金額は不要です。

採点

あなたのソリューションは、一連のテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功する必要があります。

サンプルの説明

最初の例では、4日間有効の1枚のチケットを$8$で購入するのが最も安いです。

2番目の例では、1日有効の2枚のチケットを合計$12$で購入するのが最も安いです。

3番目のサンプルでは、4日間有効のチケットを$7$で購入するのが最も安いです（ルナは第1日に仕事に行くので）。

4つ目のサンプルでは、第$1$日に1日有効なチケットと第$5$日に5日間有効なチケットを購入するのが最も安く、合計で$6$の費用がかかります。

2 2 1
1 4
1 4
6 8
5

8

2 2 1
1 4
1 4
6 14
5

12

2 2 1
1 4
1 4
6 14
1

7

4 2 0
1 5 6 7
1 5
2 4

6