Min_cost_flow(Opencup)

#include <algorithm>
#include <cstdio>

using namespace std;

const int INF = 1000000000, N = 222, M = 111111;
int n, m, first[N], next[M], ev[M], ec[M], es[M], S, T, ef[M], from[N], edge[N], d[N], c;

void add(int x, int y, int z, int co) {
    next[++c] = first[x]; first[x] = c;
    ef[c] = x; es[c] = y; ev[c] = z; ec[c] = -co;
}

int be(int x) {
    if (x & 1) return x + 1;
    return x - 1;
}

void clear_graph() {
    for (int i = 0; i <= T; ++i) first[i] = from[i] = edge[i] = 0;
    for (int i = 0; i <= c; ++i) ef[i] = ev[i] = ec[i] = es[i] = next[i] = 0;
    c = 0;
}

void fb() {
    for (int i = 1; i <= T; ++i) d[i] = INF;
    d[S] = 0;
    for (int i = 1; i <= T; ++i) {
        bool ch = false;
        for (int j = 1; j <= c; ++j) {
            if (ev[j] && d[es[j]] > d[ef[j]] + ec[j] && d[ef[j]] != INF) {
                d[es[j]] = d[ef[j]] + ec[j];
                from[es[j]] = ef[j];
                edge[es[j]] = j;
                ch = true;
            }
        }
        if (!ch) break;
    }
}

int solve() {
    int res = 0;
    while (1) {
        fb();
        if (d[T] == INF) break;
        for (int v = T; v != S; v = from[v]) {
            --ev[edge[v]];
            ++ev[be(edge[v])];
        }
        res += d[T];
    }
    return -res;
}

int main() {
    while (1) {
        scanf("%d%d",&n, &m);
        if (n == 0) break;
        clear_graph();
        S = n + m + 1;
        T = n + m + 2;
        for (int i = 1; i <= n; ++i) {
            int x;
            scanf("%d", &x);
            add(m + i, T, x, 0);
            add(T, m + i, 0 ,0);
        }
        for (int i = 1; i <= m; ++i) {
            add(S, i, 1, 0);
            add(i, S, 0, 0);
        }
        for (int i = 1; i <= m; ++i) {
            int y, c1, c2, c3, c4;
            scanf("%d%d%d%d%d", &y, &c1, &c2, &c3, &c4);
            ++c1;++c2;++c3;++c4;
            int f = y * 4;
            add(i, m + c1, 1, f);
            add(m + c1, i, 0, -f);
            add(i, m + c2, 1, f - 1);
            add(m + c2, i, 0, -f + 1);
            add(i, m + c3, 1, f - 2);
            add(m + c3, i, 0, -f + 2);
            add(i, m + c4, 1, f - 3);
            add(m + c4, i, 0, -f + 3);
        }
        printf("%d\n", solve());
    }
    return 0;
}