说明

Franklin 正在玩一款最新的潮流计时动作视频游戏，他需要面对一个 Boss 连战：在这个艰难挑战中，他必须击败 $N$ 只怪物（即 Boss）才能存活下来。他唯一的技能 格挡 极其强大，但很难使用。

每个 Boss 每隔 $d$ 秒攻击 Franklin 一次；不过，Boss 在开始攻击序列之前有各自的 起始延迟，这使得 Boss 的攻击时间错开。更具体地说，若 $f_i$ 是第 $i$ 个 Boss 的起始延迟，那么该 Boss 将在如下时刻发动攻击：

为了防御，Franklin 可以在攻击发生的精确秒数上进行格挡，从而瞬间击败该 Boss，并使其后续所有攻击不再发生。Franklin 一次只能格挡一次攻击：如果多个 Boss 同时攻击他，他最多只能格挡其中一次攻击。

此外，格挡一次攻击后，Franklin 会进入疲惫状态，在接下来的 $w$ 秒内无法再次格挡。形式化地说，如果 Franklin 在第 $t$ 秒格挡了一次攻击，那么他下一次可以格挡的最早时刻是第 $t+w$ 秒。

Franklin 有充足的生命值，并不在意 Boss 对他的攻击，但他希望尽快结束战斗。请计算在最优格挡策略下，Franklin 击败所有 $N$ 个 Boss 所需的最短时间。

输入格式

输入的第一行包含三个空格分隔的整数 $N$ $(1 \leq N \leq 3\cdot 10^5)$、$w$ $(1 \leq w \leq 10^9)$ 和 $d$ $(1 \leq d \leq 10^9)$，其中 $N$ 是 Boss 的数量，$w$ 是 Franklin 格挡后必须等待才能再次格挡的秒数，$d$ 是同一个 Boss 两次攻击之间的间隔秒数。

接下来一行包含 $N$ 个空格分隔的整数 $f_i$ $(0 \leq f_i < d)$，表示每个 Boss 的起始延迟秒数。

输出格式

输出一个整数，表示在最优格挡策略下 Franklin 击败所有 $N$ 个 Boss 所需的秒数。

3 4 10
2 3 8

12

3 4 10
2 3 9

13

提示

样例输入 1 解释

第一个 Boss 在第 $2$ 秒攻击 Franklin；Franklin 可以格挡这次攻击，但他选择等待，改为格挡第二个 Boss 在第 $3$ 秒的攻击。此时他进入疲惫状态，在第 $7$ 秒之前无法再次格挡。

第三个 Boss 在第 $8$ 秒攻击 Franklin，Franklin 格挡了这次攻击。他再次进入疲惫状态，直到第 $12$ 秒才能再次格挡：正好赶上格挡第一个 Boss 的第二次攻击，从而结束战斗。

翻译由 DeepSeek V3.2 完成