Iron Bars

Time Limit : 3 sec, Memory Limit : 262144 KB

鉄の棒

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

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

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

Input

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

N M X Y
a_1
a_2
:
a_N
b_1
b_2
:
b_M

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

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-11-3
http://web-ext.u-aizu.ac.jp/pc-concours/