#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;const int N=100005;const long long inf=(long long )N*(long long )N;long long a[N],f[N],t[N],q[N];int main(){ int n,l,r,i,x,y; long long k,ans,p; while (scanf("%d%d%d%lld",&n,&l,&r,&p)==4) { for (i=1; i<=n; i++) scanf("%lld",&a[i]); k=a[1]; for (i=2; i<=n-l; i++) { f[i]=k; if (k+p<a[i]) k+=p; else k=a[i]; } k=a[n]; for (i=n-1; i>=l+1; i--) { t[i]=k; if (k+p<a[i]) k+=p; else k=a[i]; } x=1; y=0; ans=inf; for (i=l+1; i<=n-1; i++) { while (y>=x && f[q[y]]>f[i-l+1]) y--; q[++y]=i-l+1; while (q[x]<i-r+1) x++; ans=min(ans,f[q[x]]+t[i]); } printf("%lldn",ans); }}
