//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

using namespace std;
const int inf = 1e9;
namespace flow {
    const int maxm = 5005;
    const int maxn = 305;
    struct edge
    {
        int u, v, c;
        edge *rev;
        edge *next;
    }pool[maxm * 2], *h[maxn];
    int cnt = 0;
    void clr() {
        for (int i = 0; i < maxn; i++)
            h[i] = NULL;
        cnt = 0;
    }
    void addedge(int u, int v, int c)
    {
        //cout<<"ADE"<<u<<" "<<v<<" "<<c<<endl;
        edge *new1 = &pool[cnt++];
        new1->u = u, new1->v = v, new1->c = c;
        
        edge *new2 = &pool[cnt++];
        new2->u = v, new2->v = u, new2->c = 0;
        
        new1->rev = new2, new2->rev = new1;
        new1->next = h[u], h[u] = new1;
        new2->next = h[v], h[v] = new2;
    }
    int level[maxn], q[maxn], fr, ed;
    int s, t;
    void bfs()
    {
        fr = ed = 0;
        memset(level, -1, sizeof(level));
        level[s] = 1, q[ed++] = s;
    
        while(fr < ed)
        {
            for(edge *p = h[q[fr]]; p; p = p->next)
            {
                if(!p->c || level[p->v] != -1) continue;
                level[p->v] = level[q[fr]] + 1, q[ed++] = p->v;
            }
            fr++;
        }
    }
    int dfs(int a, int flow)
    {
        if(!flow) return 0;
        if(a == t) return flow;
        int nf = 0;
        for(edge *p = h[a]; p; p = p->next)
        {
            if((level[p->v] != level[a] + 1) || (p->c <= 0)) continue;
            int nflow = dfs(p->v, min(flow - nf, p->c));
            nf += nflow, p->c -= nflow, p->rev->c += nflow;
        }
        if(!nf) level[a] = -1;
        return nf;
    }
    int dinic()
    {
        int ans = 0;
        while(1)
        {
            bfs();
            int nans = dfs(s, inf);
            if(!nans) break;
            ans += nans;
        }
        return ans;
    }
}
const int maxn = 2005;
int x[10], y[10], z[10];
int n, m, k;
int cnt[maxn][65];
bool check(int x) {
    flow::clr();
    int s = (1 << k) + k + 1, t = s + 1;
    flow::s = s, flow::t = t;
    for (int i = 0; i < k; i++)
        flow::addedge(s, i, z[i]);
    for (int i = 0; i < (1 << k); i++) {
        flow::addedge(i + k, t, cnt[x][i]);
        for (int j = 0; j < k; j++)
            if (i & (1 << j))
                flow::addedge(j, i + k, inf);
    }
    int ans = flow::dinic();
    if (ans == n * m) return 1;
    return 0;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++)
            scanf("%d%d%d", &x[i], &y[i], &z[i]);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                vector<pi> cur(k);
                for (int q = 0; q < k; q++)
                    cur[q] = mp(abs(i - x[q]) + abs(j - y[q]), q);
                sort(cur.begin(), cur.end());
                int tot = 0;
                for (int i = 0; i < cur.size(); i++) {
                    tot += (1 << cur[i].se);
                    cnt[cur[i].fi][tot]++;
                    if (i != k - 1)
                        cnt[cur[i + 1].fi][tot]--;
                }
            }    
        for (int i = 1; i < maxn; i++)
            for (int j = 0; j < (1 << k); j++)
                cnt[i][j] += cnt[i - 1][j];
        int l = 0, r = maxn - 1;
        if (!check(r)) printf("-1\n");
        else {
            while (l < r) {
                int mid = (l + r) >> 1;
                if (check(mid)) r = mid;
                else l = mid + 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}