AT_codequeen2026_b バレエの練習

プリンセスの高橋さんは、 $ T $ 秒間のバレエの演目を練習しています。 高橋さんは $ 1 $ 秒ごとに、左足と右足を独立に**浮かせる**か**地面につける**かを選べます。ただし、 $ K+1 $ 秒以上連続で両足を**浮かせる**ことはできません。 演目には、足の動かし方について次の $ N+M $ 個の指示があります。 - 各 $ i\ (1\le i\le N) $ について、 $ L_i $ 秒目に左足を**浮かせる** - 各 $ i\ (1\le i\le M) $ について、 $ R_i $ 秒目に右足を**浮かせる** 指示された秒に指示された足を浮かせているならば、その指示を満たしたものとします。 満たすことのできる指示の個数の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ T $ $ K $ $ L_1 $ $ L_2 $ $ \ldots $ $ L_N $ $ R_1 $ $ R_2 $ $ \ldots $ $ R_M $

満たすことのできる指示の個数の最大値を出力せよ。

### Sample Explanation 1 例えば、左足を $ 1, 2, 3 $ 秒目、右足を $ 2, 5 $ 秒目に浮かせれば「 $ 3 $ 秒目に右足を**浮かせる**」を除いた $ 5 $ 個の指示を満たせます。 このとき、加えて $ 3 $ 秒目に右足を**浮かせる**ことはできません。なぜなら $ 2, 3 $ 秒目の $ 2 ~ ( = K+1) $ 秒連続で両足を**浮かせる**ことになるためです。 ### Sample Explanation 2 左足を $ 1,2,3,4,5,6,7,10 $ 秒目、右足を $ 1,2,4,5,7 $ 秒目に浮かせれば $ 12 $ 個の指示を満たせます。 また、指示のない秒に足を浮かせても構いません。 ### Constraints - $ 1 \le N,M \le 2 \times 10^5 $ - $ 1 \le K \le T \le 10^9 $ - $ 1 \le L_1 \lt L_2 \lt \cdots \lt L_N\le T $ - $ 1 \le R_1 \lt R_2 \lt \cdots \lt R_M\le T $ - 入力はすべて整数である