#include <bits/stdc++.h>
constexpr int P = 1000000007;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        int n, m, k;
        std::cin >> n >> m >> k;
        std::vector<int> x(k), y(k), z(k);
        for (int i = 0; i < k; ++i) {
            std::cin >> x[i] >> y[i] >> z[i];
            --x[i];
            --y[i];
        }
        auto check = [&](int d) {
            std::vector<int> cnt(1 << k);
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    int mask = 0;
                    for (int p = 0; p < k; ++p)
                        if (std::abs(i - x[p]) + std::abs(j - y[p]) <= d)
                            mask |= 1 << p;
                    ++cnt[mask];
                }
            }
            for (int s = 0; s < (1 << k); ++s) {
                int l = 0, r = 0;
                for (int i = 0; i < k; ++i)
                    if (s >> i & 1)
                        r += z[i];
                for (int t = 0; t < (1 << k); ++t)
                    if ((s & t) == t)
                        l += cnt[t];
                if (l > r)
                    return false;
            }
            return true;
        };
        int l = 0, r = 2000;
        while (l < r) {
            int m = (l + r) / 2;
            if (check(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        if (l == 2000)
            l = -1;
        std::cout << l << "\n";
    }
    return 0;
}