/*
 * =template=.cpp
 * Copyright (C) 2017 hzw <hzw@huzhenweideMacBook.local>
 *
 * Distributed under terms of the MIT license.
 */

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cassert>
#define FR first
#define SC second
#define MP make_pair
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define ws wss
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
template<class T> void upmax(T &a,T b) { if (a<b) a=b;}
template<class T> void upmin(T &a,T b) { if (a>b) a=b;}
void read(int &x)
{
    char ch;int fu=1;
    while ((ch=getchar())<=32);
    x=0;
    if (ch=='-') fu=-1;else x=ch-48;
    while ((ch=getchar())>32) x=x*10+ch-48;
    x*=fu;
}
const double pi=acos(-1);
void upmax(int &a,int b) { if (a<b) a=b;}
void upmin(int &a,int b) { if (a>b) a=b;}
//-----------------------
const int N=5010;
struct Edge{int y,z,ne;};
int n,m,k,cas, num;
Edge e[N];int last[N];
int x[10],y[10],z[10];
int S,T,c[1000];
void add(int x,int y,int z)
{
    e[++num]=(Edge){y,z,last[x]};last[x]=num;
    e[++num]=(Edge){x,0,last[y]};last[y]=num;
}
queue<int> Q;
int d[200];
int bfs()
{
    for (int i=1;i<=200;i++)
        d[i]=-1;
    while (!Q.empty()) Q.pop();
    d[S]=0;
    Q.push(S);
    while (!Q.empty())
    {
        int now=Q.front();Q.pop();
        for (int j=last[now];j;j=e[j].ne)
            if (e[j].z&&d[e[j].y]==-1)
            {
                d[e[j].y]=d[now]+1;
                Q.push(e[j].y);
                if (e[j].y==T) return 1;
            }
    }
    return 0;
}
int dfs(int i,int low)
{
    if (i==T) return low;
    int ans=0;
    for (int j=last[i];j;j=e[j].ne)
        if (e[j].z&&d[e[j].y]==d[i]+1)
        {
            int tmp=dfs(e[j].y, min(low, e[j].z));
            e[j].z-=tmp;
            e[j^1].z+=tmp;
            ans+=tmp;
            low-=tmp;
            if (low==0) break;
        }
    return ans;
}
int check(int mid)
{
    for (int i=0;i<=200;i++)
        last[i]=c[i]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            int tp=0;
            for (int l=0;l<k;l++)
                if (abs(i-x[l])+abs(j-y[l])<=mid)
                    tp |= 1<<l;
            c[tp]++;
        }
    num = 1;S=k+(1<<k)+1;T=S+1;
    for (int i=0;i<k;i++)
        add(S, i+1, z[i]);
    for (int i=0;i<(1<<k);i++)
        add(i+k+1, T, c[i]);
    for (int i=0;i<k;i++)
        for (int j=0;j<(1<<k);j++)
            if ((1<<i)&j)
                add(i+1, j+k+1, z[i]);
    int ans=0;
    while (bfs())
        ans += dfs(S, 1<<30);
  //  printf("%d %d\n", mid, ans);
    if (ans==n*m)
        return 1;
    else
        return 0;
}
int main()
{
    scanf("%d", &cas);
    
    for (int ii=1;ii<=cas;ii++)
    {
        scanf("%d%d%d", &n, &m, &k);
        int s=0;
        for (int i=0;i<k;i++)
        {
            scanf("%d%d%d", &x[i],&y[i],&z[i]);
            s+=z[i];
        }
        if (s<n*m)
        {
            puts("-1");
            continue;
        }
        int l=0, r=n*m;
        while (l<r)
        {
            int mid=(l+r)/2;
            if (check(mid))
                r=mid;
            else l=mid+1;
        }
        printf("%d\n", l);
    }
    return 0;
}