/*最大重量封闭图；

意甲冠军：一些城市要建路需要负责一些公司，每家公司都需要缴纳个税。该公司将需要花费每路，另一个限制条件，如果那家公司a既定a-b。公司b既定b-c然后选择

公司a 你必须选择一个公司b。

今天，最大的收入要求.

解：设置一个源点和汇点，将选每一个公司的收益和算出来，假设为正值和源点相连。假设为负值和和汇点相连权值为其绝对值。中间的公司之间有关系的权值置为inf，

最大权闭合图=全部正收益的和-最小割.

*/

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

#define N  5100//注意数组要开够

#define inf 0x3fffffff

int f[N],n,m,toa[N*5],nexta[N*5],heada[N*5],tob[N*5],nextb[N*5],headb[N*5],yonga,yongb;//临界表模拟容器

int fee[N*5],s,t;

struct node {

 int u,v,w,next;

}bian[N*6+N*5*2];

int head[N],yong,dis[N];

void init(){//初始化

yong=0;

memset(head,-1,sizeof(head));

memset(dis,-1,sizeof(dis));

memset(toa,0,sizeof(toa));

memset(tob,0,sizeof(tob));

memset(heada,-1,sizeof(heada));

memset(headb,-1,sizeof(headb));

yonga=yongb=0;

memset(nexta,0,sizeof(nexta));

memset(nextb,0,sizeof(nextb));

}

void addfa(int u,int v) {

toa[yonga]=v;

nexta[yonga]=heada[u];

heada[u]=yonga++;

}

void addfb(int u,int v) {//临界表a

tob[yongb]=v;

nextb[yongb]=headb[u];

headb[u]=yongb++;

}

void addedge(int u,int v,int w) {//临界表b

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

void add(int u,int v,int w) {

addedge(u,v,w);

addedge(v,u,0);

}

/*isap模板*/

void bfs() {

int u,v,i;

queue<int>q;

q.push(t);

dis[t]=0;

while(!q.empty()) {

    u=q.front();

    q.pop();

    for(i=head[u];i!=-1;i=bian[i].next) {

        v=bian[i].v;

        if(dis[v]==-1) {

            dis[v]=dis[u]+1;

            q.push(v);

        }

    }

}

return ;

}

int ISAP() {

int sum=0;

bfs();

int  gap[N],cur[N],stac[N],top,i;

memset(gap,0,sizeof(gap));

for(i=s;i<=t;i++) {

    gap[dis[i]]++;

    cur[i]=head[i];

}

int k=s;

top=0;

while(dis[s]<t+1) {

     if(k==t) {

            int minn=inf,index;

        for(i=0;i<top;i++) {

            int e=stac[i];

            if(minn>bian[e].w) {

                minn=bian[e].w;

                index=i;

            }

        }

        for(i=0;i<top;i++) {

            int e=stac[i];

            bian[e].w-=minn;

            bian[e^1].w+=minn;

        }

        sum+=minn;

        top=index;

        k=bian[stac[top]].u;

     }

     for(i=cur[k];i!=-1;i=bian[i].next) {

       int  v=bian[i].v;

        if(bian[i].w&&dis[k]==dis[v]+1) {

            cur[k]=i;

            k=v;

            stac[top++]=i;

            break;

        }

     }

     if(i==-1) {

        int m=t+1;

        for(i=head[k];i!=-1;i=bian[i].next)

            if(m>dis[bian[i].v]&&bian[i].w) {

                m=dis[bian[i].v];

                cur[k]=i;

            }

            if(--gap[dis[k]]==0)break;

            gap[dis[k]=m+1]++;

            if(k!=s)

                k=bian[stac[--top]].u;

     }

}

return sum;

}

//模板

void build() {

  int i,j,k;

  for(i=1;i<=n;i++)

    for(j=heada[i];j!=-1;j=nexta[j])

    for(k=headb[i];k!=-1;k=nextb[k])//

       add(tob[k],toa[j],inf);//以城市a结束的点的公司连接以城市a開始的点的公司

}

int main(){

   int i,k,u,v,w,f,sum;

   while(scanf("%d%d",&n,&m),n||m) {

        init();

            sum=0;

        for(i=1;i<=m;i++)

            scanf("%d",&fee[i]);

        scanf("%d",&k);

        while(k--) {

            scanf("%d%d%d%d",&u,&v,&w,&f);

         addfa(u,w);//以u开头的公司

         addfb(v,w);//以v结束的公司

             fee[w]-=f;//选每一个公司可获得的收益

        }

        s=0;t=m+1;

        for(i=1;i<=m;i++) {

            if(fee[i]>0) {//假设为正，与源点相连

            add(s,i,fee[i]);

            sum+=fee[i];//计算全部权值为正的

            }

            else

            add(i,t,-fee[i]);//假设为负将权值的绝对值与t相连

        }

        build();

        sum=sum-ISAP();

        if(sum<=0)//假设没有收益输出0

        printf("0\n");

            else

        printf("%d\n",sum);

   }

return 0;

}