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

namespace mxfl{
  const int N=100, M=1e4;
  typedef int str;
  const str inf=1e9;
  
  struct E{
    int to; str fl; int nex;
  }e[M];
  int n, hea[N], cne, cur[N], st, en, d[N];
  void init(int n_=N-1){
    n=n_; cne=1;
    memset(hea,0,sizeof (int)*(n+1));
  }
  void adde(int u,int v,str w,str bw=0){
    e[++cne]=(E){v,w,hea[u]}; hea[u]=cne;
    e[++cne]=(E){u,bw,hea[v]}; hea[v]=cne;
  }
  bool bfs(){
    memset(d,33,sizeof d); d[st]=0;
    queue<int>q; q.push(st);
    for (int x,y,z;!q.empty();){
      x=q.front(); q.pop(); if (x==en) return 1;
      for (int i=hea[x];i;i=e[i].nex){
        if (!e[i].fl) continue;
        y=e[i].to; z=d[x]+1;
        if (z<d[y]) d[y]=z, q.push(y);
      }
    }
    return 0;
  }
  str dfs(int x,str F){
    if (x==en||!F) return F;
    str las=F;
    for (int &i=cur[x];i;i=e[i].nex){
      int y=e[i].to;
      if (!e[i].fl||d[y]!=d[x]+1) continue;
      str t=dfs(y,min(las,e[i].fl));
      las-=t; e[i].fl-=t; e[i^1].fl+=t;
      if (!las) break;
    }
    return F-las;
  }
  str realmain(int st_,int en_){
    st=st_; en=en_;
    str ans=0;
    for (;bfs();){
      memcpy(cur,hea,sizeof (int)*(n+1));
      ans+=dfs(st,inf);
    }
    return ans;
  }
}

int T, n, m, k, a[8], b[8], c[8], f[66];

bool chk(int d){
    memset(f,0,sizeof f);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j){
            int S=0;
            for (int w=0;w<k;++w){
                int t=abs(i-a[w])+abs(j-b[w]);
                if (t<=d) S|=1<<w;
            }
            if (!S) return 0;
            ++f[S];
        }
    mxfl::init();
    int st=64, en=65, bas=66;
    for (int w=0;w<k;++w){
        mxfl::adde(st,w+bas,c[w]);
        for (int S=0;S<(1<<k);++S)
            if (S>>w&1){
                mxfl::adde(w+bas,S,f[S]);
            }
    }
    for (int S=1;S<(1<<k);++S)
        if (f[S]) mxfl::adde(S,en,f[S]);
    int res=mxfl::realmain(st,en);
    return res==n*m;
}

int main(){
    for (cin>>T;T--;){
        cin>>n>>m>>k;
        for (int i=0;i<k;++i)
            cin>>a[i]>>b[i]>>c[i];
        int tot=0;
        for (int i=0;i<k;++i) tot+=c[i];
        if (tot<n*m){
            puts("-1"); continue;
        }
        int l=0, r=n+m, ans=r;
        for (;l<=r;){
            int mid=l+r>>1;
            if (chk(mid)){
                r=mid-1; ans=mid;
            }else{
                l=mid+1;
            }
        }
        cout<<ans<<endl;
    }
}