 #include <stdio.h>
#include <string.h>
#define LL __int64
const int N = 100005;
int n;
LL m, s, c;
LL A[N], dp[N];
LL sum[N];
int que[N];
int pre[N];
int seg[N][2];
  LL ok(int i, int j)  {
 return (dp[j] - dp[i]) + s * (A[j+1] - A[i+1]);
 }
int main() {
  while( scanf("%d%I64d%I64d%I64d", &n, &m, &s, &c) != EOF) {
sum[0] = 0ll;
for(int i = 1; i <= n; i ++) {
scanf("%d", A + i);
sum[i] = sum[i - 1] + A[i];
 }
int head = 0, tail = 0;
dp[0] = 0ll;
que[0] = 0;
pre[0] = 0;
for(int i = 1; i <= n; i ++) {
while( head <= tail && sum[i] - sum[que[head]] > m ) head++;
pre[i] = que[head];
dp[i] = dp[que[head]] + s*(A[que[head] + 1] - A[i]) + c;
while( head <= tail && ok(que[tail], i) >= 0 ) tail --;
que[++tail] = i;
}
int cnt = 0, t = n;
t = n;
while( t != 0) {
seg[cnt][0] = pre[t]+1;
seg[cnt++][1] = t;
t = pre[t];
}
printf("%I64d %d\n", dp[n] + sum[n], cnt);
for(int i = cnt - 1; i >= 0; i --) printf("%d %d\n", seg[i][0], seg[i][1]);
puts("");
}
}
|