【题目描述】

两只小青蛙𝐴 和 𝐵 想从河的一端跳到另一端，它们分别选择了一条道路，每条道路上都有𝑛 个石子，𝐴 在第一条道路上进行跳跃，𝐵在第二条道路上进行跳跃。双方不能跳到对方的道路上，青蛙只能跳到石子上，不能跳到河里。青蛙只能前进，不能后退，可以一次跳过多个石子，不必逐个石子向前跳。青蛙的跳跃距离至多为𝑚，但是他们有一个助跳器，可以让自己的跳跃距离上限变为𝑘(𝑚 < 𝑘)。

初始时跳跃器在青蛙𝐴 手中，它们虽然不在一个道路上，但是可以相互传递跳跃器。即 𝐴 可以将跳跃器传给𝐵，𝐵 也可以将跳跃器传给𝐴。但是如果他们距离之差超过𝑞(𝑘 < 𝑞)，则无法传递。

请问两只青蛙都跳到终点(第𝑛 个石子)最少需要传递几次助跳器？

保证相邻石子的距离之差小于𝑘，可以证明两只青蛙一定可以都抵达终点。

【输入格式】

第一行输入四个正整数𝑛, 𝑚, 𝑘, 𝑞。

接下来一行包含𝑛 个正整数，分别表示第一只青蛙面前的 𝑛 颗石头到起点的距离，第𝑖 个正整数为 𝑎𝑖(1 ≤𝑎𝑖 ≤ 10^6 )，保证对于任意的 𝑖，有 𝑎𝑖 < 𝑎𝑖+1。

接下来一行包含𝑛 个正整数，分别表示第二只青蛙面前的 𝑛 颗石头到起点的距离，第𝑖𝑖 个正整数为 𝑏𝑖 (1 ≤𝑏𝑖 ≤ 10^6 )，保证对于任意的 𝑖，有 𝑏𝑖 < 𝑏𝑖+1。

【输出格式】

输出一行一个整数表示答案。

【样例 1 输入】

4 2 5 10
5 10 15 20
2 4 6 8

【样例 1 输出】

0

【样例 1 说明】

𝐴 拿着助跳器直接跳到终点，而 𝐵 面前的石子距离较近，可以直接跳，所以𝐵可以不借助助跳器直接跳到终点。共传递 0 次助跳器。

【样例 2 输入】

4 2 5 10
5 10 15 20
5 10 15 20

【样例 2 输出】

2

【样例 2 说明】

青蛙𝐴 先走到第二颗石头（位置10），此时将助跳器传递给青蛙𝐵；青蛙𝐵 跳到终点（位置 20）再将助跳器传递给 𝐴，𝐴 跳到终点注意：若𝐴 直接跳到终点，则此时助跳器传递不到 𝐵（因为两青蛙此时的距离大于 𝑞），𝐵 无法抵达终点。

【样例 3 输入】

4 2 5 6
4 8 12 14
5 10 15 20

【样例 3 输出】

3

【样例 3 说明】

𝐴 跳一次之后传给 𝐵，𝐵 跳两次到 10，此时两青蛙距离是 10 − 4 = 6，刚好可以传递，再由𝐵 传递给 𝐴，让 𝐴 一直跳到终点（14），𝐴 再传递给𝐵 让 𝐵跳到终点。共传递 3 次。

【样例 4 输入】

4 3 6 7
4 5 9 11
5 11 16 19

【样例 4 输出】

3

【数据范围】

本题共有 10 个测试点

对于 1 − 2 的测试点，有 1 ≤𝑛, 𝑚, 𝑘, 𝑞 ≤ 8

对于 3 − 4 测试点，有𝑎𝑛 ≤ k

对于 5 − 7 测试点，有 1 ≤𝑛, 𝑚 ≤ 80, 𝑚 < 𝑘< 𝑞 ≤ 300

对于 100% 的数据，有 1 ≤𝑛, 𝑚, 𝑘, 𝑞 ≤ 1000, 𝑚 < 𝑘 < q