J問題 - Herbicide

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

T君はとある自動車販売店に勤めています。ある日こんなプログラム(TrumpScript)が送られてきました。

    # Make TrumpScript great again!
    wall = '\u9664\u8349' * 9
    tremendous = '\u7dba\u9e97' * 9

    # Print the Trump-ish pattern
    tell wall + tremendous + wall
    America is great.

そこでT君は

大変申し訳ございません。直ちに除草徹底いたします。

と返信しました。

「直ちに」徹底するため、T君は除草について調べてみました。するとこの世界の木は「複数の木がつながっている」ということがわかりました。そしてT君は「女装王」という一度に複数の繋がった木を除草できる最強の除草剤があることを知りました。例えば\(A\)と\(B\)の木がつながっていた時、\(A\)に除草剤を掛けるだけで二つの木を除草することができ、さらに\(C\)という木もつながっていれば\(A,B,C\)の3つの木を一度にまとめて除草できます。

T君は優秀な社員なので自店舗だけではなく同じ道の他店舗でも「環境整備活動」を行おうと考えています。具体的にはその店舗から\(P\)ずつ離れた(合計で\(1+2P\)の範囲)店舗の前の木を「環境整備」しようと考えています。

店舗は\(N\)店舗、木は\(M\)本あり、店舗、木の位置は道の一番左を\(0\)としてそれぞれ\(B_i\),\(T_j\)(\(1 \leq i \leq N\),\(1 \leq j \leq M\))として与えられます。

また、事前の調査によって木\(u_k\)と木\(u_k\)(\(1 \leq k \leq X\))が繋がっているということが分かっています。(木の連結関係は\(X\)個あります。)

T君は除草剤費を自腹で払うよう指導されているので、T君の自腹です。そのため、できるだけ使用する除草剤の量を少なくしたいです。

最小の除草剤購入数を求めてください。ただし、除草剤1つにつき1回の除草ができます。

制約

• \(1 \leq N \leq 100\)
• \(1 \leq M \leq 10^5\)
• \(1 \leq B_i,T_j \leq 10^9\)
• \(1 \leq u_k,v_k \leq M\)
• \(1 \leq X \leq 10^5\)
• \(1 \leq P \leq 10^9\)

入力

N M X P
B_1 B_2 ... B_N
T_1 T_2 ... T_M
u_1 v_1
u_2 v_2
...
u_X v_X

出力

使用する除草剤の量を最小にすることができる除草剤の購入数を1行で出力せよ。

入力例1

3 5 3 2
5 10 30
1 6 10 11 26
1 2
1 4
2 4

出力例1

2

2番目と3番目,または2番目と4番目の木に除草剤をかけることで目的を達成することができます。