#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<queue>#include<string>#include<iostream>using namespace std;int n,m,q;int e[110],f[110],r[10];struct X{    int a,b,z,d;    int nx;}ee[11000];struct Y{    int id,st,dis;    Y(int ID,int ST,int DIS)    {        id=ID;        st=ST;        dis=DIS;    }    bool operator <(const Y&y) const    {        return dis>y.dis;    }};int h[110], dis[110][20000];int t[10];void dij(){    for(int i=0;i<n;i++)        for(int j=0;j<t[m];j++)            dis[i][j]=0x7FFFFFFF;    dis[0][0]=0;    priority_queue<Y>Q; Q.push(Y(0,0,0));    while(!Q.empty())    {        Y q = Q.top(); Q.pop();        if(q.dis>dis[q.id][q.st]) continue;        if(q.id==n-1)        {            printf("%d\n",q.dis);            return ;        }        for(int i=h[q.id];i!=-1;i=ee[i].nx)        {            int tmp=q.st;            for(int j=0;j<m;j++) r[j]=tmp%3,tmp/=3;            int cost = ee[i].d, v = 1;            if(r[ee[i].z]==1) cost += e[ee[i].z];            else if(r[ee[i].z]==2) cost += f[ee[i].z],v=0;            if(q.dis+cost<dis[ee[i].b][q.st+v*t[ee[i].z]])            {                dis[ee[i].b][q.st+v*t[ee[i].z]] = q.dis+cost;                Q.push(Y(ee[i].b,q.st+v*t[ee[i].z],dis[ee[i].b][q.st+v*t[ee[i].z]]));            }        }    }}int main(){    t[0]=1; for(int i=1;i<=9;i++) t[i]=3*t[i-1];    while(~scanf("%d%d%d",&n,&m,&q))    {        for(int i=0;i<m;i++) scanf("%d",&e[i]);        for(int i=0;i<m;i++) scanf("%d",&f[i]);        memset(h,-1,sizeof h);        for(int i=1;i<=q;i++)        {            scanf("%d%d%d%d",&ee[i].a,&ee[i].b,&ee[i].z,&ee[i].d);            ee[i].nx = h[ee[i].a];            h[ee[i].a]=i;        }        dij();    }    return 0;}