Juanzhang

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
int n, k, L, R, sum[maxn];

struct RMQ {
  int lg[maxn], st[20][maxn];
  int get_max(int x, int y) {
    return sum[x] < sum[y] ? y : x;
  }
  void build() {
    st[0][1] = 1;
    for (int i = 2; i <= n; i++) {
      st[0][i] = i;
      lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i < 20; i++) {
      for (int j = 1; j + (1 << i) - 1 <= n; j++) {
        st[i][j] = get_max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  int query(int l, int r) {
    int k = lg[r - l + 1];
    return get_max(st[k][l], st[k][r - (1 << k) + 1]);
  }
} ST;

struct node {
  int st, l, r, pos;
  node(int _s = 0, int _l = 0, int _r = 0) :
    st(_s), l(_l), r(_r), pos(ST.query(_l, _r)) {}
  int get_val() const {
    return sum[pos] - sum[st - 1];
  }
  bool operator < (const node& o) const {
    return get_val() < o.get_val();
  }
};

priority_queue <node> Q;

int main() {
  scanf("%d %d %d %d", &n, &k, &L, &R);
  for (int i = 1; i <= n; i++) {
    scanf("%d", sum + i), sum[i] += sum[i - 1];
  }
  ST.build();
  for (int i = 1; i <= n - L + 1; i++) {
    Q.push(node(i, i + L - 1, min(n, i + R - 1)));
  }
  long long ans = 0;
  while (k--) {
    node p = Q.top();
    ans += p.get_val(), Q.pop();
    if (p.l < p.pos) Q.push(node(p.st, p.l, p.pos - 1));
    if (p.pos < p.r) Q.push(node(p.st, p.pos + 1, p.r));
  }
  printf("%lld", ans);
  return 0;
}