#include <bits/stdc++.h>
using namespace std;
int n, m, k, x[10], y[10], z[10], sum[64], ps[64];
inline bool check(int lim) {
    memset(sum, 0, 4 * (1 << k));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int cur = 0;
            for (int l = 1; l <= k; l++) {
                if (abs(x[l] - i) + abs(y[l] - j) <= lim) cur ^= (1 << (l - 1));
            }
            if (!cur) return false;
            sum[cur]++;
        }
    }
    for (int i = 0; i < k; i++) {
        for (int mask = 0; mask < (1 << k); mask++) if (mask >> i & 1) sum[mask] += sum[mask ^ (1 << i)];
    }
    for (int mask = 1; mask < (1 << k); mask++) {
        if (sum[mask] > ps[mask]) return false;
    }
    return true;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        int sss = 0;
        for (int i = 1; i <= k; i++) scanf("%d%d%d", &x[i], &y[i], &z[i]), sss += z[i];
        if (sss < n * m) {
            puts("-1");
            continue;
        }
        for (int i = 1; i <= k; i++) ps[1 << (i - 1)] = z[i];
        for (int mask = 1; mask < (1 << k); mask++) {
            ps[mask] = ps[mask & (mask - 1)] + ps[mask ^ (mask & (mask - 1))];
        }
        int lo = 0, hi = n + m - 2;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (check(mid)) hi = mid;
            else lo = mid + 1;
        }
        printf("%d\n", hi);
    }
    return 0;
}