← 返回题目列表

Codeforces · 883/A

A. 自动门

中文机器翻译题面 查看原题

工厂入口处有一扇自动门。门的工作原理如下:

- 当一个或几个人来到门前并且门关闭时,门立即自动打开,所有人立即进来,
- 当一个或几个人来到门前并且门打开时,所有人立即进来,
- 打开的门在打开后 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。同一时刻,客户也会到来,因此首先他会进入,只有在之后门才会关闭。这样门就会打开一次。