409942: GYM103860 L Paid Leave

Nikuniku is working in a factory with a brutal work schedule. She has to work every day from 00:00 to 00:00 (the next day). Such a work schedule is known as 007. To keep her efficiency high, she knows she needs to choose to take a break on some days. Fortunately, there are some legal holidays that she doesn't need to go to work. Moreover, she can choose some working days to rest and still get paid, known as paid leave.

Nikuniku needs to make a plan for the following $$$n$$$ days, enumerated from $$$1$$$ to $$$n$$$. We already know there are $$$m$$$ legal holidays on the $$${p_1}$$$th, $$$\dots$$$, $$${p_m}$$$th day. Now Nikuniku needs to choose some extra days as paid leave days. Specifically, she wants the schedule of the $$$n$$$ days to satisfy the following two conditions:

• Any period of consecutive working days should not exceed $$$x$$$ days.
• If there are $$$a$$$ consecutive working days just before a single rest day, and $$$b$$$ consecutive working days right after this rest day, the sum of $$$a$$$ and $$$b$$$ must not exceed $$$y$$$. (Note: Both legal holidays and paid leave days are considered rest days)

Nikuniku wants you to calculate the minimum paid leave days she needs to take following the above conditions.

There are four integers $$$n$$$ ($$$1 \leq n \leq {10}^{18}$$$), $$$m$$$ ($$$0 \leq m \leq \min(n, 2 \cdot 10^5)$$$), $$$x$$$, $$$y$$$ ($$$1 \leq x \leq y \leq \min(2 \cdot x, {10}^{18})$$$) in the first line.

There are $$$m$$$ integers in the second line: $$$p_1, \dots, p_m$$$ ($$$1 \leq p_1 < \dots < p_m \leq n$$$), indicating all legal holidays.

Output the answer in one line.

8 0 3 3

2

11 1 2 4
6

2

17 2 5 7
6 12

1