#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define inv2 500000004
#define last last2
#define FR first
#define SE second

using namespace std;

typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef pair<int,int> pr;

struct Edge {
  int t,f,next;
  Edge() {}
  Edge(int a,int b,int c):t(a),f(b),next(c) {}
};

Edge e[1000005];
int head[105],vs,vt,tot;

inline void addEdge(int x,int y,int z) {
  e[++tot]=Edge(y,z,head[x]);
  head[x]=tot;
  e[++tot]=Edge(x,0,head[y]);
  head[y]=tot;
}

namespace Flow {

int d[105],cur[105];
queue <int> q;

bool bfs() {
  while (!q.empty()) q.pop();
  memset(d,255,sizeof(d));
  d[vs]=0;cur[vs]=head[vs];
  q.push(vs);
  while (!q.empty()) {
      int x=q.front();q.pop();
      for(int i=head[x];i!=-1;i=e[i].next)
        if (e[i].f&&d[e[i].t]==-1) {
              int u=e[i].t;
              d[u]=d[x]+1;
              cur[u]=head[u];
              if (u==vt) return 1;
              q.push(u);
        }
  }
  return 0;
}

int dfs(int x,int a) {
  if (x==vt||!a) return a;
  int ans=0;
  for(int &i=cur[x];i!=-1;i=e[i].next)
    if (e[i].f&&d[e[i].t]==d[x]+1) {
        int u=e[i].t;
        int f=dfs(u,min(a,e[i].f));
        if (f) {
            e[i].f-=f;
            e[i^1].f+=f;
            ans+=f;
            a-=f;
            if (!a) break;
        }
    }
  return ans;
}

int maxflow() {
  int ans=0;
  while (bfs())
    ans+=dfs(vs,inf);
  return ans;
}

} 

pr num[10];
int val[10];

bool check(int n,int m,int k,int d) {
  int cnt[64];
  memset(cnt,0,sizeof(cnt));
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
      int st=0;
      for(int l=0;l<k;l++)
        if (abs(i-num[l].FR)+abs(j-num[l].SE)<=d) st|=(1<<l);
      cnt[st]++;
    }
  memset(head,255,sizeof(head));
  tot=-1;
  vs=0;vt=k+(1<<k)+1;
  for(int i=0;i<(1<<k);i++) {
      addEdge(vs,i+1,cnt[i]);
    for(int j=0;j<k;j++)
      if ((i>>j)&1) addEdge(i+1,(1<<k)+j+1,inf);
  }
  for(int i=0;i<k;i++) addEdge((1<<k)+i+1,vt,val[i]);
  return Flow::maxflow()==n*m;
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
      int n,m,k;
      scanf("%d%d%d",&n,&m,&k);
      int s=0;
      for(int i=0;i<k;i++) {
      scanf("%d%d%d",&num[i].FR,&num[i].SE,&val[i]);
      s+=val[i];
    }
    if (s<n*m) {
        puts("-1");
        continue;
    }
      int l=0,r=n+m;
      while (l<r) {
          int mid=((l+r)>>1);
          if (check(n,m,k,mid)) r=mid; else l=mid+1;
      }
    printf("%d\n",l);
  }
  return 0;
}