#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
ll gi(){
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))f^=ch=='-',ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
    int ret=1;
    while(y){
        if(y&1)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;y>>=1;
    }
    return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int px[10],py[10],pz[10],cnt[1<<6];
int fir[80],head[80],dep[80],dis[100010],nxt[100010],id=1;
ll w[100010];
void link(int a,int b,ll c){
    nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;
    nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0;
}
int S=1,T=2;
bool BFS(){
    static int que[80],hd,tl;hd=tl=0;
    memset(dep+1,0,sizeof dep);dep[S]=1,que[tl++]=S;
    while(hd^tl){
        int x=que[hd++];
        for(int i=fir[x];i;i=nxt[i])if(w[i]&&!dep[dis[i]])dep[dis[i]]=dep[x]+1,que[tl++]=dis[i];
    }
    return dep[T];
}
ll Dinic(int x,ll maxflow){
    if(x==T)return maxflow;
    ll ret=0;
    for(int&i=head[x];i;i=nxt[i])
        if(w[i]&&dep[dis[i]]==dep[x]+1){
            ll d=Dinic(dis[i],std::min(w[i],maxflow-ret));
            w[i]-=d,w[i^1]+=d,ret+=d;if(ret==maxflow)break;
        }
    return ret;
}
int main(){
#ifdef LOCAL
    freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
#endif
    int qwq=gi();
    while(qwq--){
        int n=gi(),m=gi(),k=gi(),sum=0;
        for(int i=0;i<k;++i)px[i]=gi(),py[i]=gi(),pz[i]=gi(),sum+=pz[i];
        if(sum<n*m){puts("-1");continue;}
        int l=1,r=n+m,mid;
        while(l<r){
            mid=l+r>>1;
            memset(cnt,0,sizeof cnt);
            for(int i=1;i<=n;++i)
                for(int j=1;j<=m;++j){
                    int S=0;
                    for(int s=0;s<k;++s)if(abs(px[s]-i)+abs(py[s]-j)<=mid)S|=1<<s;
                    ++cnt[S];
                }
            memset(fir,0,sizeof fir);id=1;
            for(int i=1;i<=k;++i)link(1,i+2,pz[i-1]);
            for(int i=0;i<1<<k;++i)if(cnt[i])link(k+3+i,2,cnt[i]);
            for(int i=0;i<1<<k;++i)for(int j=0;j<k;++j)if(i>>j&1)link(j+3,k+3+i,1e9);
            int ans=0;while(BFS())memcpy(head,fir,sizeof head),ans+=Dinic(S,1e9);
            if(ans==n*m)r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}