Dinner

Time Limit : 4 sec, Memory Limit : 131072 KB

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

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

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

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

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

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

Input

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

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

Constraints

  • 1 ≤ N ≤ 500,000
  • 0 ≤ P ≤ 500,000
  • |Q| ≤ 500,000
  • |Ci| ≤ 500,000

Output

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

Sample Input 1

1 1 1
2

Output for the Sample Input 1

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

Sample Input 2

3 2 1
3
3
3

Output for the Sample Input 2

12
  • このケースでは毎日自炊をするのが最適で,幸福度は 2 × 1 + 2 × 2 + 2 × 3 = 12 となる.

Sample Input 3

3 1 -1
2
-3
2

Output for the Sample Input 3

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

Sample Input 4

3 1 -10
-10
-10
-10

Output for the Sample Input 4

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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 4, Tokyo, Japan, 2014-09-15
http://acm-icpc.aitea.net/
http://jag2014summer-day4.contest.atcoder.jp/