#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
    static ui seed=416;
    return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1666;
int n,m,k,A[N],B[N],C[N];
int Abs(int x){return x>0?x:-x;}
bool ck(int lim){
    static int f[1<<6|3];memset(f,0,sizeof(f));
    rep(i,1,n)rep(j,1,m){
        int s=0;rep(c,1,k)s|=(Abs(A[c]-i)+Abs(B[c]-j)<=lim)<<c-1;
        f[s]++;
    }
    rep(s,0,(1<<k)-1){
        int sum=0;rep(i,1,k)if(s>>i-1&1)sum+=C[i];
        int tot=0;for(int t=s;;t=(t-1)&s){tot+=f[t];if(!t)break;}
        if(sum<tot)return 0;
    }
    return 1;
}
int main() {
    int t;read(t);while(t--){
        read(n);read(m);read(k);int gs=0;
        rep(i,1,k)read(A[i]),read(B[i]),read(C[i]),gs+=C[i];
        if(gs<n*m){puts("-1");continue;}
        int l=0,r=n+m;
        while(l<r){
            int mid=(l+r)>>1;
            if(ck(mid))r=mid;else l=mid+1;
        }
        cout<<l<<endl;
    }
    return 0;
}