Franklin 正在玩一款最新的潮流限时动作电子游戏，他面临着一场 Boss Rush（首领连战）：这是一场艰苦的挑战，他必须击败 $N$ 个怪物（Boss）才能生存。他唯一的技能“招架”（parry）非常强大，但极难使用。

每个 Boss 每隔 $d$ 秒攻击 Franklin 一次；然而，每个 Boss 在开始攻击序列前都有各自的起始延迟，因此 Boss 的攻击是错开的。更具体地说，如果 $f_i$ 是第 $i$ 个 Boss 的起始延迟，那么该 Boss 将在以下时刻进行攻击： $$f_i, f_i + d, f_i + 2d, \dots$$

为了防御，Franklin 可以在攻击发生的瞬间进行招架，从而立即击败该 Boss 并结束其后续的所有攻击。Franklin 一次只能招架一次攻击：如果多个 Boss 同时攻击他，他最多只能招架其中一个。

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

Franklin 的生命值充足，并不担心 Boss 对他的攻击，但他希望尽快结束战斗。请计算如果 Franklin 采取最优招架策略，击败所有 $N$ 个 Boss 所需的最短时间。

输入格式

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

第二行包含 $N$ 个空格分隔的整数 $f_i$ ($0 \le f_i < d$)，表示每个 Boss 的起始延迟（以秒为单位）。

输出格式

输出 Franklin 采取最优策略击败所有 $N$ 个 Boss 所需的秒数。

说明

样例 1 的解释： 第一个 Boss 在第 2 秒攻击 Franklin；Franklin 本可以招架这次攻击，但他选择等待，转而在第 3 秒招架第二个 Boss 的攻击。此时他进入气喘状态，在第 7 秒之前无法再次招架。 第三个 Boss 在第 8 秒攻击 Franklin，Franklin 招架了这次攻击。他再次进入气喘状态，直到第 12 秒才能再次招架：这正好赶上招架第一个 Boss 的第二次攻击，从而结束了战斗。

样例

输入 1

3 4 10
2 3 8

输出 1

12

输入 2

3 4 10
2 3 9

输出 2

13