012 - 鉄の棒

時間制限 3 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
3sec
MLE
256MB
得点
12

PCK 君は1 番からN 番までの番号が付いたN 本のまっすぐな鉄の棒を持っていましたが、運搬中に1 番目からM 番目までのM 本が折れ曲がってしまいました(0 ≤ MN)。折れ曲がった棒は、どれも1箇所で直角に曲がっています。

PCK 君は折れ曲がった棒の中からX 本、まっすぐな棒からY 本を、2X+Y=12 を満たすようにそれぞれ選び、それらをすべて使って直方体を1つ作ろうとしています。ただし、棒をつなげるのは、直方体の頂点だけです。PCK 君は、そのようにして作ることのできる直方体の形がいくつあるか数えようとしています。

鉄の棒の本数と長さ、折れ曲がっている位置、直方体を作るのに使う棒の数が与えられたとき、作ることのできる直方体の形がいくつあるか求めるプログラムを作成せよ。ただし、ある直方体i と別の直方体j の幅、奥行き、高さをそれぞれ小さい順に並べたものをAi, Bi, CiAj, Bj, Cj としたとき、Ai=Aj かつBi=Bj かつCi=Cj となる直方体は同じ形とみなす。また、どの鉄の棒も十分細いので、太さは無視することができるものとする。

Input

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

N M X Y
a1
a2
:
aN
b1
b2
:
bM

1行目に、鉄の棒の数N (6 ≤ N ≤ 6000)と折れ曲がった棒の数M (0 ≤ MN)、直方体を作るのに使う折れ曲がった棒の数X (0 ≤ X ≤ 6)とまっすぐな棒の数Y (0 ≤ Y ≤ 12)が与えられる。ただし、2X+Y=12X+YNXM である。続くN 行にi 番目の鉄の棒の長さを表す整数ai (1 ≤ ai ≤ 6000)がcm 単位で与えられる。続くM 行に、1 番目からM 番目までの鉄の棒が折れ曲がっている位置を表す整数bi (1 ≤ bi ≤ 3000)が与えられる。bii 番目の鉄の棒が端から bi cm のところで直角に折れ曲がっていることを表す。ただし、1 ≤ aibi ≤ 3000 である。

Output

直方体の形の個数を1行に出力する。

Sample Input 1

18 8 3 6
4
3
3
3
3
2
2
2
1
1
1
1
1
2
2
3
3
3
1
1
1
1
1
1
1
1

Sample Output 1

3