MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

2014年春，ある学生は無事大学に合格し，一人暮らしを始める事となった．ここで問題となるのが夕食をどうするかである．彼はこれから $N$ 日間の夕食の計画を立てる事にした．

彼は $N$ 日間で得られる幸福度の合計を出来る限り大きくしたい．もちろん，美味しいものや好きなものを食べるほど幸福度は高い．

彼の夕食の選択肢は2つ，近くの食堂に向かうか，自炊をするかのどちらかである．

食堂で得られる幸福度は，その日のメニューによって変わる．メニューは日替わりだが毎日一種類のみで，$N$ 日間のメニューは全て既に公開されている．なので，彼は $i$ 日目 ($1 \\leq i \\leq N$) に食堂に行けば $C\_i$ の幸福度を得られるという情報を全て知っている．

自炊で得られる幸福度は，その自炊の開始時点での自炊パワーに定数 $P$ を掛けたものである．自炊パワーは初期値が $Q$ であり，毎日，食堂に行けば-1，自炊をすれば+1，その日の食事の終了時に変動する．

彼のために幸福度の総和の最大値を求めよう．

Input

入力は以下の形式で $N+1$ 行で与えられる．

$N$ $P$ $Q$
$C\_1$
$C\_2$
:
:
$C\_N$

• 1行目は3つの整数 $N, P, Q$ が与えられ，それぞれ日数，自炊の幸福度を算出するための定数，自炊パワーの初期値である．
• 2行目から $N+1$ 行目にはそれぞれ整数が1つずつ与えられ，$i+1$ 行目では $i$ 日目に食堂に行った時に得られる幸福度が与えられる．

Constraints

• $1 \\leq N \\leq 500{,}000$
• $0 \\leq P \\leq 500{,}000$
• $|Q| \\leq 500{,}000$
• $| C\_i | \\leq 500{,}000$

Output

幸福度の取りうる最大値を一行に出力せよ．

Sample Input 1

1 1 1
2```

### Output for the Sample Input 1

```plain
2```

*   考えるべき予定は1日だけである．食堂に行けば2，自炊すると1の幸福度なので，答えは2となる．

* * *

### Sample Input 2

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

### Output for the Sample Input 2

```plain
12```

*   このケースでは毎日自炊をするのが最適で，幸福度は $2 \\times 1+2 \\times 2+2 \\times 3 = 12$となる．

* * *

### Sample Input 3

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

### Output for the Sample Input 3

```plain
2```

*   2日目のみで自炊をすることが最善となる．

* * *

### Sample Input 4

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

### Output for the Sample Input 4

```plain
-27```

*   答えが負になることもある．いくらまずくても夕食は食べなければならない．

* * *