题目描述

DL24JP C2 教学楼有一部电梯，
你现在要乘坐这部电梯来到四楼参加信息学体验活动 。

电梯的容量是无限的，电梯内外都有开门键和关门键。
当任意的开门键被按下，电梯门会立刻开始匀速开启，直到电梯门完全打开，电梯门从完全关闭到完全打开需要 $s$ 秒。类似的，当任意关门键被按下，电梯门会立刻开始匀速关闭，直到电梯门完全关闭，电梯门从完全打开到完全关闭也需要 $s$ 秒 。
电梯门完全关闭后：所有按键失效，电梯门不再打开，电梯开始上升，花费 $p$ 秒将电梯内的人运载到四楼。
只有电梯门完全打开时，人才可以进入。你可以在任意时间按下任意电梯按键 。

当然，参加信息学体验活动的人除了你之外还有 $n$ 个。当他们中的任意一个人来到电梯门前，他会立刻按下开门键，直到自己能够进入电梯，他将立即进入电梯。
你是所有人中第一个来到电梯前的，你刚刚走进电梯，现在电梯门完全打开，现在的时刻为 0 秒。
你获得了 yzy 给予你的超能力： 你提前知晓了其他参加信息学体验活动的人到达电梯前的时刻。具体地，第 $i$ 个人到达电梯门前的时刻为 $t_{i}$ (数据保证 $t_{i}$ 严格不降，详见数据范围与提示) 。

特别地，如果存在一个时刻 $T$，在电梯门完全关闭的同时，电梯的开门按键被按下，那么认为电梯门没有完全关闭，电梯门将匀速打开，电梯将不会上升；电梯内除了你之外的人不会按下任何按键。

现在你想知道：你最早在什么时刻到达四楼？

输入格式

共两行，
第一行三个整数 $n,\,s,\,p$ ,
第二行 $n$ 个整数，分别表示 $t_{1} , t_{2} , \ ... \ ,t_{n-1} , t_{n}$ 。

输出格式

一行一个整数，表示你最早到达四楼的时刻。

输入输出样例

2 4 5
2 4 

13

3 3 3
3 6 10

12

数据范围和提示

样例解释

样例 1 解释

一种可能的情况：
第 0 秒，你保持电梯门开启。
第 2 秒，第一个人到达电梯前，由于你保持电梯门开启，这个人直接进入电梯。
第 4 秒，同理，第二个人直接进入电梯，你紧接着按下关门键，电梯门开始匀速关闭。
第 8 秒，电梯门完全关闭，电梯开始上升。
第 13 秒，电梯到达四楼，可以证明没有更优情况。

样例 2 解释

一种可能的情况：
第 0 秒，你按下关门键。
第 3 秒，电梯门刚好完全关闭，但此时第一个人到达电梯门前按下开门键，电梯门匀速打开。
第 6 秒，第二个人到达电梯前，电梯门刚好完全打开，两人进入电梯，同时，你按下关门键。
第 9 秒，电梯门完全关闭，此时电梯前没有人，电梯开始上升。
第 10 秒，第三个人到达电梯前，但此时电梯已在上升过程中。
第 12 秒，电梯到达四楼，可以证明没有更优情况。

数据范围

对于 $40\%$ 的数据，保证 $1\leq n\leq10^5,\ 1\leq s\leq 10^5,\ 1\leq p\leq 10^5,\ 1\leq t_{i}\leq 10^6$，
对于另外 $20\%$ 的数据，保证 $s<t_{i}$，
对于 $100 \%$ 的数据，保证 $1\leq n\leq10^6,\ 1\leq s\leq 10^9,\ 1\leq p\leq 10^9,\ 1\leq t_{i}\leq 10^9,\ t_{i}\leq t_{i+1}\ (1\leq i \leq n-1)$。