// Created by hoangvanthien
#include "bits/stdc++.h"
using namespace std;
#define FOR(i, x, y) for(int i = (x); i<=(y); ++i)
#define REP(i, r) for(int i = 0; i < (r); ++i)
#define DFOR(i, x, y) for(int i = (x); i>=(y); --i)
#define db(x) cout << #x << " = " << x << endl;
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it!=var.end(); ++it)
#define forrit(it, var) for(__typeof(var.rbegin()) it = var.rbegin(); it!=var.rend(); ++it)
#define pb push_back
#define pf push_front
#define mp make_pair
#define F first
#define S second
#define II pair<int,int>
#define LL long long
#define lb lower_bound
#define ub upper_bound
#define LAST(x) (int)x.size()-1
#define ld long double
#define maximize(x, y) x=max(x,(y))
#define minimize(x, y) x=min(x,(y))
const int N = 502;
const int oo = 1000000007;
int n, money, R, d, e, q[6], Min[6], Max[6], ans, c[6], trace[N][6];
II p[N][6];
void attemp(int x, int y) {
if (x == R + 1) {
maximize(ans, money);
if (money == 12139) {
FOR(i, 1, R) {
FOR(j, 1, n) printf("%d ", trace[i][j]);
puts("");
}
// exit(0);
}
return;
}
if (y == n + 1) {
FOR(i, 1, n)
if (trace[x][i] > 0) money -= trace[x][i] * p[x][i].F, q[i] += trace[x][i];
else money -= trace[x][i] * p[x][i].S, q[i] += trace[x][i];
if (money < 0) {
FOR(i, 1, n)
if (trace[x][i] > 0) money += trace[x][i] * p[x][i].F, q[i] -= trace[x][i];
else money += trace[x][i] * p[x][i].S, q[i] -= trace[x][i];
return;
}
attemp(x + 1, 1);
FOR(i, 1, n)
if (trace[x][i] > 0) money += trace[x][i] * p[x][i].F, q[i] -= trace[x][i];
else money += trace[x][i] * p[x][i].S, q[i] -= trace[x][i];
return;
}
trace[x][y] = 0;
if (Min[y] >= Max[y]) {
attemp(x, y + 1);
return;
}
if (Max[y] == p[x][y].S && q[y] != 0) {
trace[x][y] = -q[y];
attemp(x, y + 1);
trace[x][y] = 0;
}
if (Min[y] == p[x][y].F) {
FOR(i, 0, c[y] - q[y]) {
trace[x][y] = i;
attemp(x, y + 1);
trace[x][y] = 0;
}
return;
}
attemp(x, y + 1);
// FOR(i, -q[y], c[y] - q[y]) {
// trace[x][y] = i;
// attemp(x, y + 1);
// trace[x][y] = 0;
// }
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.inp", "r", stdin);
// freopen("output.out", "w", stdout);
#endif // ONLINE_JUDGE
scanf("%d%d%d%d%d", &n, &money, &R, &d, &e);
FOR(i, 1, n) scanf("%d", &c[i]);
FOR(i, 1, n) Min[i] = oo, Max[i] = 0;
FOR(i, 1, R) FOR(j, 1, n) {
int x;
scanf("%d", &x);
p[i][j] = mp(x + d, x - e);
minimize(Min[j], x + d);
maximize(Max[j], x - e);
}
attemp(1, 1);
printf("%d\n", ans);
cout << endl;
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
Ly8gQ3JlYXRlZCBieSBob2FuZ3ZhbnRoaWVuCgojaW5jbHVkZSAiYml0cy9zdGRjKysuaCIKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZPUihpLCB4LCB5KSBmb3IoaW50IGkgPSAoeCk7IGk8PSh5KTsgKytpKQojZGVmaW5lIFJFUChpLCByKSBmb3IoaW50IGkgPSAwOyBpIDwgKHIpOyArK2kpCiNkZWZpbmUgREZPUihpLCB4LCB5KSBmb3IoaW50IGkgPSAoeCk7IGk+PSh5KTsgLS1pKQojZGVmaW5lIGRiKHgpIGNvdXQgPDwgI3ggPDwgIiA9ICIgPDwgeCA8PCBlbmRsOwojZGVmaW5lIGZvcml0KGl0LCB2YXIpIGZvcihfX3R5cGVvZih2YXIuYmVnaW4oKSkgaXQgPSB2YXIuYmVnaW4oKTsgaXQhPXZhci5lbmQoKTsgKytpdCkKI2RlZmluZSBmb3JyaXQoaXQsIHZhcikgZm9yKF9fdHlwZW9mKHZhci5yYmVnaW4oKSkgaXQgPSB2YXIucmJlZ2luKCk7IGl0IT12YXIucmVuZCgpOyArK2l0KQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIHBmIHB1c2hfZnJvbnQKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBJSSBwYWlyPGludCxpbnQ+CiNkZWZpbmUgTEwgbG9uZyBsb25nCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIExBU1QoeCkgKGludCl4LnNpemUoKS0xCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBtYXhpbWl6ZSh4LCB5KSB4PW1heCh4LCh5KSkKI2RlZmluZSBtaW5pbWl6ZSh4LCB5KSB4PW1pbih4LCh5KSkKCgpjb25zdCBpbnQgTiA9IDUwMjsKY29uc3QgaW50IG9vID0gMTAwMDAwMDAwNzsKaW50IG4sIG1vbmV5LCBSLCBkLCBlLCBxWzZdLCBNaW5bNl0sIE1heFs2XSwgYW5zLCBjWzZdLCB0cmFjZVtOXVs2XTsKSUkgcFtOXVs2XTsKCnZvaWQgYXR0ZW1wKGludCB4LCBpbnQgeSkgewogICAgaWYgKHggPT0gUiArIDEpIHsKICAgICAgICBtYXhpbWl6ZShhbnMsIG1vbmV5KTsKICAgICAgICBpZiAobW9uZXkgPT0gMTIxMzkpIHsKICAgICAgICAgICAgRk9SKGksIDEsIFIpIHsKICAgICAgICAgICAgICAgIEZPUihqLCAxLCBuKSBwcmludGYoIiVkICIsIHRyYWNlW2ldW2pdKTsKICAgICAgICAgICAgICAgIHB1dHMoIiIpOwogICAgICAgICAgICB9Ci8vICAgICAgICAgICAgZXhpdCgwKTsKICAgICAgICB9CgogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmICh5ID09IG4gKyAxKSB7CiAgICAgICAgRk9SKGksIDEsIG4pCiAgICAgICAgICAgIGlmICh0cmFjZVt4XVtpXSA+IDApIG1vbmV5IC09IHRyYWNlW3hdW2ldICogcFt4XVtpXS5GLCBxW2ldICs9IHRyYWNlW3hdW2ldOwogICAgICAgICAgICBlbHNlIG1vbmV5IC09IHRyYWNlW3hdW2ldICogcFt4XVtpXS5TLCBxW2ldICs9IHRyYWNlW3hdW2ldOwogICAgICAgIGlmIChtb25leSA8IDApIHsKICAgICAgICAgICAgRk9SKGksIDEsIG4pCiAgICAgICAgICAgICAgICBpZiAodHJhY2VbeF1baV0gPiAwKSBtb25leSArPSB0cmFjZVt4XVtpXSAqIHBbeF1baV0uRiwgcVtpXSAtPSB0cmFjZVt4XVtpXTsKICAgICAgICAgICAgICAgIGVsc2UgbW9uZXkgKz0gdHJhY2VbeF1baV0gKiBwW3hdW2ldLlMsIHFbaV0gLT0gdHJhY2VbeF1baV07CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgYXR0ZW1wKHggKyAxLCAxKTsKICAgICAgICBGT1IoaSwgMSwgbikKICAgICAgICAgICAgaWYgKHRyYWNlW3hdW2ldID4gMCkgbW9uZXkgKz0gdHJhY2VbeF1baV0gKiBwW3hdW2ldLkYsIHFbaV0gLT0gdHJhY2VbeF1baV07CiAgICAgICAgICAgIGVsc2UgbW9uZXkgKz0gdHJhY2VbeF1baV0gKiBwW3hdW2ldLlMsIHFbaV0gLT0gdHJhY2VbeF1baV07CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgdHJhY2VbeF1beV0gPSAwOwogICAgaWYgKE1pblt5XSA+PSBNYXhbeV0pIHsKICAgICAgICBhdHRlbXAoeCwgeSArIDEpOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmIChNYXhbeV0gPT0gcFt4XVt5XS5TICYmIHFbeV0gIT0gMCkgewogICAgICAgIHRyYWNlW3hdW3ldID0gLXFbeV07CiAgICAgICAgYXR0ZW1wKHgsIHkgKyAxKTsKICAgICAgICB0cmFjZVt4XVt5XSA9IDA7CiAgICB9CgogICAgaWYgKE1pblt5XSA9PSBwW3hdW3ldLkYpIHsKICAgICAgICBGT1IoaSwgMCwgY1t5XSAtIHFbeV0pIHsKICAgICAgICAgICAgdHJhY2VbeF1beV0gPSBpOwogICAgICAgICAgICBhdHRlbXAoeCwgeSArIDEpOwogICAgICAgICAgICB0cmFjZVt4XVt5XSA9IDA7CiAgICAgICAgfQogICAgICAgIHJldHVybjsKICAgIH0KICAgIGF0dGVtcCh4LCB5ICsgMSk7Ci8vICAgIEZPUihpLCAtcVt5XSwgY1t5XSAtIHFbeV0pIHsKLy8gICAgICAgIHRyYWNlW3hdW3ldID0gaTsKLy8gICAgICAgIGF0dGVtcCh4LCB5ICsgMSk7Ci8vICAgICAgICB0cmFjZVt4XVt5XSA9IDA7Ci8vICAgIH0KfQoKaW50IG1haW4oKSB7CiNpZm5kZWYgT05MSU5FX0pVREdFCiAgICBmcmVvcGVuKCJpbnB1dC5pbnAiLCAiciIsIHN0ZGluKTsKLy8gICAgZnJlb3Blbigib3V0cHV0Lm91dCIsICJ3Iiwgc3Rkb3V0KTsKI2VuZGlmIC8vIE9OTElORV9KVURHRQogICAgc2NhbmYoIiVkJWQlZCVkJWQiLCAmbiwgJm1vbmV5LCAmUiwgJmQsICZlKTsKICAgIEZPUihpLCAxLCBuKSBzY2FuZigiJWQiLCAmY1tpXSk7CiAgICBGT1IoaSwgMSwgbikgTWluW2ldID0gb28sIE1heFtpXSA9IDA7CiAgICBGT1IoaSwgMSwgUikgRk9SKGosIDEsIG4pIHsKICAgICAgICAgICAgaW50IHg7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZ4KTsKICAgICAgICAgICAgcFtpXVtqXSA9IG1wKHggKyBkLCB4IC0gZSk7CiAgICAgICAgICAgIG1pbmltaXplKE1pbltqXSwgeCArIGQpOwogICAgICAgICAgICBtYXhpbWl6ZShNYXhbal0sIHggLSBlKTsKICAgICAgICB9CiAgICBhdHRlbXAoMSwgMSk7CiAgICBwcmludGYoIiVkXG4iLCBhbnMpOwoKICAgIGNvdXQgPDwgZW5kbDsKICAgIGNlcnIgPDwgIlRpbWUgZWxhcHNlZDogIiA8PCAxLjAgKiBjbG9jaygpIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgIiBzLlxuIjsKfQ==