#include <cstdio>
#include <algorithm>
using namespace std;

#define forn( i,n ) for ( int i=0; i<(int)(n); i++ )

const int inf = (int)1e9;

int n, m, a, b, f[110][110][22], ci, cj, ans;
int cntI[110], cntJ[110], x[22], y[22];

void precalc()
{
  for ( int n=1; n<=100; n++ )
    for ( int m=1; m<=100; m++ )
      for ( int k=1; k<=20; k++ )
        if ( k > n*m ) f[n][m][k] = inf;
        else f[n][m][k] = min( f[n-1][m][k-min(k,m)] + m, f[n][m-1][k-min(k,n)] + n );
}

void check()
{
  int cur = ci * m + cj * n - ci * cj;
  if ( cur >= a+b ) ans = min( ans, cur );
  else ans = min( ans, cur + f[n-ci][m-cj][a+b-cur] );
}

void rec( int i )
{
  if ( i == a ) check();
  else
  {
    if ( cntI[x[i]] == 0 ) ci++;
    cntI[x[i]]++;
    rec( i+1 );
    cntI[x[i]]--;
    if ( cntI[x[i]] == 0 ) ci--;

    if ( cntJ[y[i]] == 0 ) cj++;
    cntJ[y[i]]++;
    rec( i+1 );
    cntJ[y[i]]--;
    if ( cntJ[y[i]] == 0 ) cj--;
  }
}

void solve()
{
  scanf( "%d %d %d %d", &n, &m, &a, &b );
  forn( i, a ) scanf( "%d %d %*d", &x[i], &y[i] );

  forn( i, n ) cntI[i] = 0;
  forn( j, m ) cntJ[j] = 0;

  ans = inf;
  ci = 0, cj = 0;
  rec( 0 );
  printf( "%d\n", ans );
}

int main()
{
  precalc();

  int tc;
  scanf( "%d", &tc );
  while ( tc-- ) solve();
}