mangoes

/*
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 15 May 2023 [19:55]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int i,j,w;
};
A trees[100010];
int qs[5010][5010];
int main(){
    int n,m,R,C;
    cin >> n >> m >> R >> C;
    for(int i=1;i<=n;i++)
        cin >> trees[i].i >> trees[i].j >> trees[i].w;
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        qs[u][v]++;
    }
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            qs[i][j] += qs[i-1][j] + qs[i][j-1] - qs[i-1][j-1];
    int l = 1,r = max(R,C);
    while(l<r){
        int mid = (l+r)/2;
        int able = true;
        for(int k=1;k<=n;k++){
            int i = trees[k].i,j = trees[k].j;
            int num = qs[min(R,i+mid)][min(C,j+mid)] - qs[max(0,i-mid-1)][min(C,j+mid)] - qs[min(R,i+mid)][max(0,j-mid-1)] + qs[max(0,i-mid-1)][max(0,j-mid-1)];
            if(num < trees[k].w){
                able = 0;
                break;
            }
        }
        if(able)    r = mid;
        else        l = mid+1;
    }
    cout << l << '\n';
    return 0;
}