#include<bits/stdc++.h>
#define N 10010
using namespace std;
int T,h[N],l[N],e[N],c[N],v[N],f[N],O=1<<30,t,n,m,k,s,X[7],Y[7],K[7],TT,pp[65];
void A(int x,int y,int z){e[++t]=y,l[t]=h[x],h[x]=t,c[t]=z;e[++t]=x,l[t]=h[y],h[y]=t,c[t]=0;}
int S(int x,int F)
{
    if(x==T)return F;
    int r=0,t,i;
    for(i=h[x];i;i=l[i])if(c[i]&&f[x]==f[e[i]]+1)if(t=S(e[i],min(F-r,c[i])),c[i]-=t,c[i^1]+=t,(r+=t)>=F||f[0]>T)return r;
    if(!--v[f[x]])f[0]=T+1;++v[++f[x]];
    return r;
}
main()
{
    cin>>TT;while(TT--)
    {
        int LL=0,RR=2000,MM;
        cin>>n>>m>>k;
        for(int i=1;i<=k;i++)cin>>X[i]>>Y[i]>>K[i];
        while(LL<RR)
        {
            memset(f,0,sizeof(f));memset(v,0,sizeof(v));memset(h,0,sizeof(h));memset(pp,0,sizeof(pp));
            t=1;
            s=0;
            T=64+k+1;
            MM=(LL+RR)/2;
            for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
            {
                int tmp=1;
                for(int _=1;_<=k;_++)if(abs(X[_]-i)+abs(Y[_]-j)<=MM)tmp+=(1<<(_-1));
                pp[tmp]++;
            }
            for(int i=1;i<=k;i++)A(64+i,T,K[i]);
            for(int i=1;i<=64;i++)
            {
                A(0,i,pp[i]);
                for(int j=1;j<=k;j++)if(((i-1)>>(j-1))&1)A(i,64+j,O);
            }
            while(f[0]<=T)s+=S(0,O);
            if(s==n*m)RR=MM;else LL=MM+1;
        }
        if(LL==2000)cout<<-1<<endl;else cout<<LL<<endl;
    }
}