AT_icpc2014summer_day4_d 夕食

2014年春天，一个学生顺利考上了大学，开始一个人生活，这里面出现问题是晚饭怎么办?他决定今后制定N天的晚饭计划。 他想尽可能地扩大在N天能得到的幸福度.当然，越吃好吃的东西和喜欢的东西幸福度越高. 他晚饭有两个选择，是去附近的餐厅，还是自己做饭。 食堂获得的幸福度会根据当天的菜单而变化.菜单每天都更换,但每天仅有一种, N N天的菜单已经全部公开.所以,他i天目( 1≤i≤N )去食堂的话，Ci 全都知道能得到的幸福度. 自己做饭所得到的幸福度是自己做饭开始时在自己做饭时给自己定量的P.自己做饭的初始值为Q,每天去食堂的话-1,自己做饭的话+1,当天吃饭结束时变动. 为他求得幸福度总和的最大值

入力は以下の形式で N+1 行で与えられる． 输入以以下的形式N+1行给予 N P Q C1 C2 : : CN - 第1行提供3个整数N, P, Q分别为天数,用于计算自己做饭的幸福度的常数,自己做饭的能量的初始值. - 从第2行开始N+1行分别给出整数1个，第i+1行给出i i天去食堂时得到的幸福度. 限制: - 1 ≤ N ≤ 500,000 - 0 ≤ P ≤ 500,000 - ∣Q∣ ≤ 500,000 - ∣Ci∣≤500,000 第1行提供3个整数N, P, Q N, P, Q,分别为天数,用于计算自己做饭的幸福度的常数,自己做饭的能量的初始值. 从第2行开始N+1 N+1行分别给出整数1个，第i+1 i+1行给出i i天去食堂时得到的幸福度.

把能获得幸福度的最大值输出一行.