Juanzhang

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

typedef double db;
const int maxn = 2010;
int n, m, W, AP[maxn], BP[maxn], AS[maxn], BS[maxn], Q[maxn], f[maxn][maxn];

inline void chkmax(int &x, int y) {
  if (x < y) x = y;
}

int main() {
  scanf("%d %d %d", &n, &m, &W);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d %d %d", AP + i, BP + i, AS + i, BS + i);
  }
  int ans = 0;
  memset(f, -0x3f, sizeof f);
  f[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    memset(Q, 0, sizeof Q);
    int l = 1, r = 1;
    int pos = max(0, i - W - 1);
    for (int j = 0; j <= m; j++) {
      if (Q[l] < j - AS[i]) l++;
      chkmax(f[i][j], f[pos][Q[l]] + (Q[l] - j) * AP[i]);
      while (l <= r && f[pos][Q[r]] + Q[r] * AP[i] <= f[pos][j] + j * AP[i]) r--;
      Q[++r] = j;
    }
    l = 1, r = 1, Q[1] = m;
    for (int j = m; ~j; j--) {
      if (Q[l] > j + BS[i]) l++;
      chkmax(f[i][j], f[pos][Q[l]] + (Q[l] - j) * BP[i]);
      while (l <= r && f[pos][Q[r]] + Q[r] * BP[i] <= f[pos][j] + j * BP[i]) r--;
      Q[++r] = j;
    }
    for (int j = 0; j <= m; j++) {
      chkmax(f[i][j], f[i - 1][j]), chkmax(ans, f[i][j]);
    }
  }
  printf("%d", ans);
  return 0;
}