#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;
}