#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

struct node { int x,y,z; }h[10];

vector<pii> v[2010];

int cnt[64];
int from[1010][1010],t,n,m,K;

inline int rd()
{
    int x=0;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

inline bool check(int mid)
{
    memset(cnt,0,sizeof(cnt));
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
    {
        int now=0;
        for (int k=1;k<=K;k++) if (abs(i-h[k].x)+abs(j-h[k].y)<=mid) now|=(1<<(k-1));
        cnt[now]++;
    }
    int res=n*m;
    for (int i=0;i<(1<<K);i++)
    {
        int sum=0;
        for (int j=1;j<=K;j++) if (!((i>>(j-1))&1)) sum+=h[j].z;
        for (int j=0;j<(1<<K);j++) if (j&i) sum+=cnt[j];
        res=min(res,sum);
    }
    return res==n*m;
}

inline void work()
{
    n=rd();m=rd();K=rd();
    for (int i=1;i<=K;i++) h[i].x=rd(),h[i].y=rd(),h[i].z=rd();
    int l=0,r=n+m;
    while (l<r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    if (!check(l)) puts("-1");
    else printf("%d\n",l);
}

int main()
{
    t=rd();
    while (t--) work();
    return 0;
}