Automatic Door

## 题目描述 工厂里有一个自动门： - 如果门关着，并来了一个或多个人，门立即打开，所有人立刻进去。 - 如果门开着，并来了一个或多个人，所有人立即进去。 - 门打开后$d$ 秒立刻关上。 - 门在关的瞬间，如果来了一个或多个人，这些人立刻进去，之后门关上。 例如，$d=3$ 时，有四个人分别在以下时刻到来：$\{4,7,9,13\}$ ， 那么门会开三次：$\{4,9,13\}$ ， 门会在以下时刻关闭：$\{7,12\}$ 。 你提前知道了公司有一批员工分别在$a,2a,3a,\cdots ,na(a\in \mathbf{Z^+})$ 时刻到来。另外有$m$ 位顾客分别在$t_{1},t_{2},\cdots,t_{m}$ 时刻到来。 最初门是关闭的。 试问门会开几次。 ## 输入格式 第一行$n,m,a,d(1\le n,a\le 10^{9},1\le m\le 10^{5},1\le d\le 10^{18})$ ，分别代表有$n$ 个员工，$m$ 个顾客，第一个员工来的时间$a$ ，和，门开的持续时间$d$ 。 第二行$m$ 个数$t_{1},t_{2},...,t_{m}(1\le t_{i}\le 10^{18})$ ，表示顾客来的时间。保证为升序排列。 ## 输出格式 输出门开的次数 翻译贡献者UID：50882

There is an automatic door at the entrance of a factory. The door works in the following way: - when one or several people come to the door and it is closed, the door immediately opens automatically and all people immediately come inside, - when one or several people come to the door and it is open, all people immediately come inside, - opened door immediately closes in $ d $ seconds after its opening, - if the door is closing and one or several people are coming to the door at the same moment, then all of them will have enough time to enter and only after that the door will close. For example, if $ d=3 $ and four people are coming at four different moments of time $ t_{1}=4 $ , $ t_{2}=7 $ , $ t_{3}=9 $ and $ t_{4}=13 $ then the door will open three times: at moments $ 4 $ , $ 9 $ and $ 13 $ . It will close at moments $ 7 $ and $ 12 $ . It is known that $ n $ employees will enter at moments $ a,2·a,3·a,...,n·a $ (the value $ a $ is positive integer). Also $ m $ clients will enter at moments $ t_{1},t_{2},...,t_{m} $ . Write program to find the number of times the automatic door will open. Assume that the door is initially closed.

The first line contains four integers $ n $ , $ m $ , $ a $ and $ d $ ( $ 1<=n,a<=10^{9} $ , $ 1<=m<=10^{5} $ , $ 1<=d<=10^{18} $ ) — the number of the employees, the number of the clients, the moment of time when the first employee will come and the period of time in which the door closes. The second line contains integer sequence $ t_{1},t_{2},...,t_{m} $ ( $ 1<=t_{i}<=10^{18} $ ) — moments of time when clients will come. The values $ t_{i} $ are given in non-decreasing order.

Print the number of times the door will open.

1 1 3 4
7

1

4 3 4 2
7 9 11

4

In the first example the only employee will come at moment $ 3 $ . At this moment the door will open and will stay open until the moment $ 7 $ . At the same moment of time the client will come, so at first he will enter and only after it the door will close. Thus the door will open one time.