#include <bits/stdc++.h>
using namespace std;
int n, m, k, more, x[6], y[6], z[6];
struct tp {
    int x, y, z;
};
bool check(int mid) {
    bitset<1000001> bs[6];
    for (int t = 0; t < k; ++t) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (abs(i - x[t]) + abs(j - y[t]) <= mid) {
                    bs[t][(i - 1) * m + j] = 1;
                }
            }
        }
    }
    for (int s = 1; s < 1 << k; ++s) {
        int ans = more;
        bitset<1000001> all;
        for (int i = 0; i < k; ++i) {
            if (s >> i & 1) {
                ans -= z[i];
                all |= bs[i];
            }
        }
        ans += all.count();
        if (ans < 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int test;
    cin >> test;
    while (test--) {
        cin >> n >> m >> k;
        more = -n * m;
        for (int i = 0; i < k; ++i) {
            cin >> x[i] >> y[i] >> z[i];
            more += z[i];
        }
        if (more < 0) {
            puts("-1");
            continue;
        }
        int l = 0, r = n + m;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        printf("%d\n", r);
    }
}