工厂入口处有一扇自动门。门的工作原理如下:
- 当一个或几个人来到门前并且门关闭时,门立即自动打开,所有人立即进来,
- 当一个或几个人来到门前并且门打开时,所有人立即进来,
- 打开的门在打开后 d 秒内立即关闭,
- 如果门正在关闭,并且一个或几个人同时来到门口,那么所有人都有足够的时间进入,只有在那之后门才会关闭。
例如,如果 d = 3,并且有四个人在 t1 = 4、t2 = 7、t3 = 9 和 t4 = 13 的四个不同时刻到来,则门将打开三次:在时刻 4、9 和 13。门将在时刻 7 和 12 关闭。
已知n个员工将在时刻a、2·a、3·a、...、n·a(a为正整数)进入。另外,m 个客户将在时刻 t1、t2、...、tm 进入。
编写程序来查找自动门打开的次数。假设门最初是关闭的。
输入
第一行包含四个整数 n、m、a 和 d(1 ≤ n、a ≤ 109、1 ≤ m ≤ 105、1 ≤ d ≤ 1018)——员工数量、客户数量、第一个员工到来的时间以及门关闭的时间段。
第二行包含整数序列 t1, t2, ..., tm (1 ≤ ti ≤ 1018) — 客户到来的时刻。 ti 值按非递减顺序给出。
输出
打印门打开的次数。
示例
输入 #1
1 1 3 4 7
输出 #1
1
输入 #2
4 3 4 2 7 9 11
输出 #2
4
注意
在第一个示例中,唯一的员工将在时刻 3 到来。此时,门将打开,并保持打开状态,直到时刻 7。同一时刻,客户也会到来,因此首先他会进入,只有在之后门才会关闭。这样门就会打开一次。