题目描述

在2014年春天，一个学生顺利通过了大学考试，开始自己独居的生活。他面临的问题是晚餐应该如何解决。他决定为接下来的$N$天制定晚餐计划。

他希望在这$N$天里获得尽可能多的幸福感。当然，吃美味的食物和喜欢的食物会让他更幸福。

他的晚餐选择有两种：去附近的食堂或者自己做饭。

在食堂就餐可以根据当天的菜单获得不同的幸福感。菜单每天都会变化，但每天只有一种菜，所有$N$天的菜单都已经公开。因此，他知道如果在第$i$天（$1 \leq i \leq N$）去食堂，他会得到$C_i$的幸福感。

自己做饭可以根据自炊能力乘以常数$P$来获得幸福感。自炊能力的初始值为$Q$，每天结束时根据当天的用餐方式变化，如果去食堂则减1，如果自己做饭则加1。

请帮助他求出幸福感总和的最大值。

输入

输入共有$N+1$行，格式如下：

$N$ $P$ $Q$
$C_1$
$C_2$
:
:
$C_N$

• 第一行包含三个整数$N, P, Q$，分别表示天数、自炊幸福感计算常数和自炊能力的初始值。
• 接下来的$N$行每行包含一个整数，表示在第$i$天（$i=1$到$N$）去食堂的幸福感。

约束条件

• $1 \leq N \leq 500,000$
• $0 \leq P \leq 500,000$
• $|Q| \leq 500,000$
• $| C_i | \leq 500,000$

输出

输出一行，表示可能的幸福感最大值。

示例输入1

1 1 1
2```

### 示例输出1

```plain
2```

* 只需要考虑一天的计划。如果去食堂，幸福感为2；如果自己做饭，幸福感为1。因此答案为2。

---

### 示例输入2

```plain
3 2 1
3
3
3```

### 示例输出2

```plain
12```

* 在这个例子中，每天都做饭是最优选择，幸福感为$2 \times 1 + 2 \times 2 + 2 \times 3 = 12$。

---

### 示例输入3

```plain
3 1 -1
2
-3
2```

### 示例输出3

```plain
2```

* 只有第二天做饭才是最佳选择。

---

### 示例输入4

```plain
3 1 -10
-10
-10
-10```

### 示例输出4

```plain
-27```

* 答案可能是负数。无论食物有多难吃，晚餐都必须吃。