/*********************************************************************
    Problem:
    Author:hydd
    Date:
*********************************************************************/
#include<cstdio>
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int T,n,m,k,upperlim;
int x[8],y[8],z[8];
int a[8][1005][1005];
int tmp[110],b[110],c[110];
inline int myabs(int x){
    if (x<0) x=-x;
    return x;
}
inline int dist(int i,int j,int x,int y){
    return myabs(i-x)+myabs(j-y);
}
bool check(int mid){
    int now;
    for (int i=0;i<=upperlim;i++) tmp[i]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            now=0;
            for (int t=1;t<=k;t++)
                if (a[t][i][j]<=mid) now|=(1<<(t-1));
            tmp[now]++;
        }
    if (tmp[0]) return false;
    upperlim=(1<<k)-1; int sum;
    for (int i=0;i<=upperlim;i++){
        sum=0;
        for (int s=i;s;s=(s-1)&i) sum+=tmp[s];
        b[i]=sum;
    }
    for (int i=0;i<=upperlim;i++)
        if (b[i]>c[i]) return false;
    return true;
}
int main(){
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);
    scanf("%d",&T);
    while (T--){
        scanf("%d%d%d",&n,&m,&k); upperlim=(1<<k)-1;
        for (int i=1;i<=k;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
        for (int i=0;i<=upperlim;i++){
            c[i]=0;
            for (int t=1;t<=k;t++)
                if (i&(1<<(t-1))) c[i]+=z[t];
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                for (int t=1;t<=k;t++)
                    a[t][i][j]=dist(i,j,x[t],y[t]);
        int l=0,r=n*m,mid;
        while (l<r){
            mid=(l+r)>>1;
            if (check(mid)) r=mid;
            else l=mid+1;
        }
        if (r==n*m) puts("-1");
        else printf("%d\n",r);
    }
    return 0;
}