#include<bits/stdc++.h>
using namespace std;

const int _ = 1e5 + 7 , __ = 2e6 + 7;
struct Edge{int end , upEd , f;}Ed[__];
int head[_] , cntEd = 1 , S , T;
void addEd(int a , int b , int c){Ed[++cntEd] = (Edge){b , head[a] , c}; head[a] = cntEd;}
void addE(int a , int b , int c){addEd(a , b , c); addEd(b , a , 0);}

int cur[_] , dep[_]; queue < int > q;
bool bfs(){
    while(!q.empty()) q.pop();
    memset(dep , 0 , sizeof(int) * (T + 1)); q.push(S); dep[S] = 1;
    while(!q.empty()){
        int t = q.front(); q.pop();
        for(int i = head[t] ; i ; i = Ed[i].upEd)
            if(Ed[i].f && !dep[Ed[i].end]){
                dep[Ed[i].end] = dep[t] + 1; q.push(Ed[i].end);
                if(Ed[i].end == T){memcpy(cur , head , sizeof(int) * (T + 1)); return 1;}
            }
    }
    return 0;
}

int dfs(int x , int mn){
    if(x == T) return mn;
    int sum = 0;
    for(int &i = cur[x] ; i ; i = Ed[i].upEd)
        if(Ed[i].f && dep[Ed[i].end] == dep[x] + 1){
            int f = dfs(Ed[i].end , min(Ed[i].f , mn - sum));
            Ed[i].f -= f; Ed[i ^ 1].f += f;
            if((sum += f) == mn) break;
        }
    return sum;
}

int Case , N , M , K , pot[1 << 6];
vector < pair < int , int > > op[2003];

int main(){
    ios::sync_with_stdio(0);
    for(cin >> Case ; Case ; --Case){
        int X[7] , Y[7] , T[7]; cin >> N >> M >> K; for(int i = 0 ; i < K ; ++i) cin >> X[i] >> Y[i] >> T[i];
        for(int i = 0 ; i <= N + M ; ++i) op[i].clear();
        memset(pot , 0 , sizeof(pot));
        for(int i = 1 ; i <= N ; ++i)
            for(int j = 1 ; j <= M ; ++j){
                int pre = 0; ++pot[0]; vector < pair < int , int > > dst;
                for(int k = 0 ; k < K ; ++k) dst.push_back(make_pair(abs(X[k] - i) + abs(Y[k] - j) , k));
                sort(dst.begin() , dst.end());
                for(int i = 0 ; i < dst.size() ; ++i){
                    op[dst[i].first].push_back(make_pair(pre , pre | 1 << dst[i].second));
                    pre |= 1 << dst[i].second;
                }
            }
        int ans = 1e9;
        for(int i = 0 ; i <= N + M ; ++i){
            for(int j = 0 ; j < op[i].size() ; ++j){
                --pot[op[i][j].first]; ++pot[op[i][j].second];
            }
            int sum = 0; ::T = K + (1 << K) + 1; S = 0; memset(head , 0 , sizeof(int) * (::T + 1)); cntEd = 1;
            for(int i = 0 ; i < K ; ++i) addE(S , i + 1 , T[i]);
            for(int i = 0 ; i < 1 << K ; ++i){
                addE(K + 1 + i , ::T , pot[i]);
                for(int j = 0 ; j < K ; ++j)
                    if(i >> j & 1) addE(j + 1 , K + 1 + i , 1e9);
            }
            while(bfs()) sum += dfs(S , 1e9);
            if(sum == N * M){ans = i; break;}
        }
        cout << (ans == 1e9 ? -1 : ans) << endl;
    }
    return 0;
}