//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <cstring>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <algorithm>

#define ll long long

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define N 8005

#define M 1000005

#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int inf = 0x3f3f3f3f;

int n,m,s,t,num;

int adj[N],dis[N],q[N];

vector<int> st[],ed[];

struct edge{

    int v,w,pre;

}e[M];

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

    e[num]=(edge){v,w,adj[u]};

    adj[u]=num++;

    e[num]=(edge){u,,adj[v]};

    adj[v]=num++;

}

int bfs(){

    int i,x,v,head=,tail=;

    memset(dis,,sizeof(dis));

    dis[s]=;

    q[tail++]=s;

    while(head<tail){

        x=q[head++];

        for(i=adj[x];~i;i=e[i].pre)

            if(e[i].w&&!dis[v=e[i].v]){

                dis[v]=dis[x]+;

                if(v==t)

                    return ;

                q[tail++]=v;

            }

    }

    return ;

}

int dfs(int x,int limit){

    if(x==t)

        return limit;

    int i,v,tmp,cost=;

    for(i=adj[x];~i&&cost<limit;i=e[i].pre)

        if(e[i].w&&dis[x]==dis[v=e[i].v]-){

            tmp=dfs(v,min(limit-cost,e[i].w));

            if(tmp){

                e[i].w-=tmp;

                e[i^].w+=tmp;

                cost+=tmp;

            }

            else

                dis[v]=-;

        }

    return cost;

}

int Dinic(){

    int ans=;

    while(bfs())

        ans+=dfs(s,inf);

    return    ans;

}

int main(){

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

        int i,j,k,u,v,c,w[]={},sum=;

        num=;

        memset(adj,-,sizeof(adj));

        s=;

        t=;

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

            st[i].clear();

            ed[i].clear();

        }

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

            scanf("%d",w+i);

            sum+=w[i];

            insert(i+,t,w[i]);

        }

        scanf("%d",&k);

        for(i=;i<=k;i++){

            scanf("%d%d%d%d",&u,&v,&c,&w[]);

            insert(s,i+m+,w[]);

            insert(i+m+,c+,inf);

            st[u].push_back(c);

            ed[v].push_back(c);

        }

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

            for(j=;j<ed[i].size();j++){

                for(k=;k<st[i].size();k++){

                    insert(st[i][k]+,ed[i][j]+,inf);          //建无穷边

                    //printf("%d %d %d\n",i,ed[i][j],st[i][k]);

                }

            }

        }

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

    }

}