#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<memory.h>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int ft(int i, int j){
    return (5-j)+(i-1)*4;
}


const int V = 140+70+2 + 10;
const int E = (V+V+V*4 + 10)*2;
int nv, S, T;
int eb[V], e[E], es[E], ed;
int ef[E], ec[E];
int ex[E], ep[V], d[V];
int fr[V];
bool u[V];

void adde(int i, int j, int c, int x, int f=0){
    ++ed;
    e[ed]=j;
    ec[ed]=c;
    ef[ed]=f;
    ex[ed]=x;
    es[ed]=eb[i];
    eb[i]=ed;

    //inv
    ++ed;
    e[ed]=i;
    ec[ed]=0;
    ef[ed]=-f;
    ex[ed]=-x;
    es[ed]=eb[j];
    eb[j]=ed;
}

pair<int, int> mcmf(){
    int inf = 1e9;
    int i,j,k;
    int cost = 0;
    int flow = 0;
    for(i=0;i<nv;++i) ep[i]=0;
    while(true){
        for(i=0;i<nv;++i) d[i]=inf, u[i]=0, fr[i]=-1;
        d[S]=0;
        for(;;){
            for(i=-1,j=0;j<nv;++j) if(!u[j] && (i<0||d[i]>d[j])) i=j;
            if(i<0||d[i]==inf) break;
            u[i]=1;
            for(k=eb[i];k;k=es[k]) if(ec[k]>ef[k]){
                j=e[k];
                if(u[j]) continue;
                int ee=d[i]+ex[k]+ep[i]-ep[j];
                if(d[j]>ee) d[j]=ee, fr[j]=k;
            }
        }
        if(d[T]==inf) return make_pair(flow, cost);
        int ff = inf;
        for(i=T; i!=S; i=e[fr[i]^1]) ff=min(ff,ec[fr[i]]-ef[fr[i]]);
        flow+=ff;
        for(i=T; i!=S; i=e[fr[i]^1]) ef[fr[i]]+=ff, ef[fr[i]^1]-=ff, cost+=ff*ex[fr[i]];
        for(i=0;i<nv;++i) ep[i]=d[i];
    }
}

int pc[V];

int main(){
    int i,j,k;
    for(;;){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n==0 && m==0) break;

        nv = n+m+2;
        S = 0;
        T = nv-1;
        for(i=0;i<nv;++i) eb[i]=0;
        ed=1;


        for(i=0;i<n;++i){
            scanf("%d",&pc[i]);
            adde(m+i+1, T, pc[i], 0);
        }

        for(i=0;i<m;++i){
            scanf("%d",&k);

            adde(S,i+1,1,0);
            for(j=0;j<4;++j){
                int w;
                scanf("%d",&w);
                ++w;
                adde(i+1,m+w,1,-ft(k,j+1));
            }
        }

        pair<int,int> res = mcmf();
        int res1 = -res.second;

        cout<<res1<<endl;
    }

    return 0;
}