#include <bits/stdc++.h> #define ll long long #define INF (1LL << 50) #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl #define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl #define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl #define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl #define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; ll A,B,W; vl d; //f[j](x)=a[j]x+b[j]でaがjの増加に伴い単調減少する場合 //0<=j<=i-kを満たす直線f[j](x)についてminをとる //maxをとる場合はcheckの不等号とsolve内のsの移動の部分の不等号を逆にする template<typename T> class CHT { public: //deqには直線のインデックスを格納 //dpの初期値はINFづめしている vector<int> deq; vector<T> a,b,dp; int n,k; CHT(vector<T>& ag1,vector<T>& ag2,int sz){ a = ag1, b = ag2; n = (int)a.size(), k = sz; deq.resize(n),dp.resize(n+1,INF); solve(); } T func(int j,int x){ return a[j]*x+b[j]; } bool check(int j1, int j2, int j3){ return (a[j2]-a[j1])*(b[j3]-b[j2]) >= (b[j2]-b[j1])*(a[j3]-a[j2]); } //今回の場合は0<=j<=i-kを満たす直線f[j](x)についてminをとっている void solve(){ dp[0] = 0, deq[0] = 0; int s = 0, t = 1; //今回の場合はb[i]の値がdp[i]の値に依存するのでb[i]を更新する rep(i,k){ b[i] += dp[i]; } //今回の問題の場合i=k~2k-1まではj=0の場合が最適であることが明らかなので //i-k<kの間はdeqに新たに直線を追加することはしない for(int i=k;i<=n;i++){ if(i-k >= k){ //末端から最小値を取る可能性がなくなったものを取り除く while(s+1 < t && check(deq[t-2],deq[t-1],i-k)){ t--; } deq[t++] = i-k; } //先頭が最小値でなければ取り除く while(s+1 < t && func(deq[s],i) >= func(deq[s+1],i)){ s++; } dp[i] = func(deq[s],i) - (i-1)*A + (i*i-i)*B/2 + d[i-1]; //今回の場合はb[i]の値がdp[i]の値に依存するのでb[i]を更新する if(i < n){ b[i] += dp[i]; } } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n >> A >> B >> W; d.resize(n); rep(i,n){ cin >> d[i]; } vector<ll> a(n), b(n); rep(i,n){ a[i] = -i*B; } rep(i,n){ b[i] = i*A+(i*i-i)*B/2; } CHT<ll> cht(a,b,1); ll ans = INF; rep(i,n){ cmn(ans,-(n-i)*A+(n-i)*(n-i+1)*B/2); } cout << W + ans << "\n"; return 0; }