#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=6;
const int X=(1<<N)+N+2;

int n,m,k;
int x[N],y[N],z[N];

int g[X][X];
int cnt;
int dis[X];
bool bfs(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        // cerr<<"b "<<x<<endl;
        q.pop();
        int d=dis[x]+1;
        for(int i=0;i<cnt;i++){
            if(g[x][i]&&dis[i]>=(int)1e9){
                dis[i]=d;
                if(i==t)return true;
                q.push(i);
            }
        }
    }
    return false;
}
int cur[X];
int dfs(int x,int t,int f){
    if(x==t)return f;
    int ans=0;
    for(int &i=cur[x];i<cnt;i++)if(dis[x]+1==dis[i]){
        int d=dfs(i,t,min(f,g[x][i]));
        ans+=d;
        f-=d;
        g[x][i]-=d;
        g[i][x]+=d;
        if(f==0)break;
    }
    return ans;
}
int dinic(int s,int t){
    // cerr<<"d "<<s<<" "<<t<<endl;
    int ans=0;
    while(bfs(s,t)){
        memset(cur,0,sizeof(cur));
        int d=dfs(s,t,1e9);
        // cerr<<d<<endl;
        ans+=d;
    }
    return ans;
}

bool test(int mx){
    memset(g,0,sizeof(g));
    int ee=1<<k;
    int st=ee+k;
    int ed=st+1;
    cnt=ed+1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        int id=0;
        for(int l=0;l<k;l++){
            if(abs(i-x[l])+abs(j-y[l])<=mx)id|=(1<<l);
        }
        g[id][ed]++;
    }
    for(int i=0;i<k;i++){
        for(int j=0;j<(1<<k);j++){
            if(j&(1<<i)){
                g[ee+i][j]=n*m;
            }
        }
        g[st][ee+i]=z[i];
    }
    int ans=dinic(st,ed);
    // cerr<<mx<<" "<<ans<<endl;
    return ans==n*m;
}

void work(){
    cin>>n>>m>>k;
    int sum=0;
    for(int i=0;i<k;i++){
        cin>>x[i]>>y[i]>>z[i];
        sum+=z[i];
    }
    if(sum<n*m){
        cout<<"-1"<<endl;
        return;
    }

    int l=0,r=n+m;
    while(l<r){
        int mid=(l+r)>>1;
        if(test(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)work();
    return 0;
}