まず、片足にしか指示がない秒については、必ずその指示を満たすことができます。したがって、以下の \(2\) つを行えばよいです。

• 両足を同時に浮かせる指示がある秒をすべて求める
• そのような秒のうち、いくつの指示を満たせるか求める

前者については、配列 \(L\) の要素をすべて set に入れ、配列 \(R\) の各要素がその set に含まれるかを確認すれば求められます。また、線形マージと同様に、\(2\) つの配列を同時に先頭から順に見る方法でも構いません。

後者については、ランレングス圧縮と同様に、両足を同時に浮かせる指示がある秒を連続する区間ごとに分けます。ある区間が \(C\) 秒続く場合、\(\left\lfloor \frac{C}{K+1} \right\rfloor\) 個の指示を無視し、それ以外の指示を満たすことが最適です。

実装例

n, m, t, k = map(int, input().split())
l = set(map(int, input().split()))
r = list(map(int, input().split()))

# 両足を同時に浮かせる指示がある秒
a = []
for x in r:
    if x in l:
        a.append(x)

ng = 0
c = 0
y = -1

for x in a:
    if y + 1 == x:
        c += 1
    else:
        ng += c // (k + 1)
        c = 1
    y = x

ng += c // (k + 1)

print(n + m - ng)