#include <bits/stdc++.h>
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define repi(i, a, b) for(int i = a; i < (int)(b); ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define inf 2147483647
#define inf64 9223372036854775807
#define Q queue
#define PQ priority_queue
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;

const int MX = 1510;

int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};

bool ok[MX][MX] = {};
bool light[MX][MX] = {};
bool wall[MX][MX] = {};
bool visited[MX][MX] = {};
bool memo[MX][MX] = {};

bool search(int k, int i, int j, int h, int w) {
    if(i < 0 || j < 0 || i >=h || j >= w) return false;
    if(wall[i][j]) return false;
    if(light[i][j]) return true;
    if(visited[i][j]) return memo[i][j];

    visited[i][j] = true;
    return memo[i][j] = search(k, i+di[k], j+dj[k], h, w);
}

void solution()
{
    int h, w, n, m;
    cin >> h >> w >> n >> m;

    rep(i, n)
    {
        int a, b;
        cin >> a >> b;

        light[a-1][b-1] = true;
    }

    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        wall[a-1][b-1] = true;
    }

    rep(k, 4) {
        rep(i, h) rep(j, w) visited[i][j] = false;
        rep(i, h) rep(j, w) if( search(k, i, j, h, w)) ok[i][j] = true;
    }

    int ans = 0;
    rep(i, h) rep(j, w) if(ok[i][j]) ++ans;

    cout << ans << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    solution();
    return 0;
}

#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
#include <cassert>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i)=0; (i) <= (n); (i)++)
#define CONTAINS_MAP(m, a) ((m).find((a)) != m.end())
#define CONTAINS_SET(m, a) ((m).find((a)) != m.end())
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; exit(0); }
void Yes() { cout << "Yes" << endl; exit(0); }
void No() { cout << "No" << endl; exit(0); }

int N, M;
int X[101];
vector<int>Y[20];
vector<int>Z[20];

int _dp[1000000];

int bit_count(ull v)
{
	ull count = (v & 0x5555555555555555ULL) + ((v >> 1ULL) & 0x5555555555555555ULL);
	count = (count & 0x3333333333333333ULL) + ((count >> 2ULL) & 0x3333333333333333ULL);
	count = (count & 0x0f0f0f0f0f0f0f0fULL) + ((count >> 4ULL) & 0x0f0f0f0f0f0f0f0fULL);
	count = (count & 0x00ff00ff00ff00ffULL) + ((count >> 8ULL) & 0x00ff00ff00ff00ffULL);
	count = (count & 0x0000ffff0000ffffULL) + ((count >> 16ULL) & 0x0000ffff0000ffffULL);
	return (int)((count & 0x00000000ffffffffULL) + ((count >> 32ULL) & 0x00000000ffffffffULL));
}

signed main()
{
	cin >> N >> M;
	//REP(i, M) cin >> X[i] >> Y[i] >> Z[i];
	REP(i, M)
	{
		int x, y, z;
		cin >> x >> y >> z;

		Y[x].push_back(y);
		Z[x].push_back(z);
	}

	int dp_max = (1LL << N);
	_dp[0] = 1;

	for (int i = 0; i < dp_max; i++)
	{
		int prev = _dp[i];

		for (int j = 0; j < N; j++)
		{
			int cur = (1LL << j);
			if ((i & cur) == 0)
			{
				int bitcnt = bit_count(i | cur);
				if (Y[bitcnt].size() == 0)
				{
					_dp[i | cur] += _dp[i];
				}
				else
				{
					bool is_valid = true;
					for (int k = 0; k < Y[bitcnt].size(); k++)
					{
						int y = Y[bitcnt][k];
						int z = Z[bitcnt][k];
						int mask = (1LL << y) - 1;
						int b = ((i | cur) & mask);
						int cnt = bit_count(b);
						if (cnt > z)
						{
							is_valid = false;
						}
					}
					if (is_valid)
					{
						_dp[i | cur] += _dp[i];
					}
				}
			}
			else
			{
			}
		}
	}

	cout << _dp[(1LL << N) - 1] << endl;
}



