#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 110

int n,m,k,l,dis[N][N][N],a[N][N],w[N][N],ans;

struct pos{int x,y;}u[N],v[N];

namespace shortestpath

{

    int d[N*N<<],p[N*N<<],t=;

    int wx[]={,,-,},wy[]={,,,-};

    bool flag[N*N<<];

    struct data{int to,nxt,len;}edge[N*N<<];

    int trans(int x,int y,int op){return op*n*m+(x-)*m+y;}

    void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

    struct data2

    {

        int x,d;

        bool operator <(const data2&a) const

        {

            return d>a.d;

        }

    };

    priority_queue<data2> q;

    void make()

    {

        for (int i=;i<=n;i++)

            for (int j=;j<=m;j++)

            {

                for (int k=;k<;k++)

                if (i+wx[k]>&&i+wx[k]<=n&&j+wy[k]>&&j+wy[k]<=m)

                if (a[i][j]<a[i+wx[k]][j+wy[k]])

                    addedge(trans(i,j,),trans(i+wx[k],j+wy[k],),),

                    addedge(trans(i,j,),trans(i+wx[k],j+wy[k],),);

                else if (a[i][j]>a[i+wx[k]][j+wy[k]])

                    addedge(trans(i,j,),trans(i+wx[k],j+wy[k],),),

                    addedge(trans(i,j,),trans(i+wx[k],j+wy[k],),);

                else

                    addedge(trans(i,j,),trans(i+wx[k],j+wy[k],),),

                    addedge(trans(i,j,),trans(i+wx[k],j+wy[k],),);

            }

    }

    void dijkstra(int start)

    {

        memset(d,,sizeof(d));d[trans(u[start].x,u[start].y,start>k)]=;

        memset(flag,,sizeof(flag));

        while (!q.empty()) q.pop();

        q.push((data2){trans(u[start].x,u[start].y,start>k),});

        for (int i=;i<=(n*m<<);i++)

        {

            while (!q.empty()&&flag[q.top().x]) q.pop();

            if (q.empty()) break;

            data2 v=q.top();q.pop();

            flag[v.x]=;

            for (int j=p[v.x];j;j=edge[j].nxt)

            if (v.d+edge[j].len<d[edge[j].to])

            {

                d[edge[j].to]=v.d+edge[j].len;

                q.push((data2){edge[j].to,d[edge[j].to]});

            }

        }

        for (int i=;i<=n;i++)

            for (int j=;j<=m;j++)

            dis[start][i][j]=min(d[trans(i,j,)],d[trans(i,j,)]);

    }

}

namespace maxflow

{

    const int S=,T=;

    int ans,p[N<<],d[N<<],q[N<<],cur[N<<],t;

    struct data{int to,nxt,cap,flow;}edge[N*N<<];

    void addedge(int x,int y,int z)

    {

        t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=,p[x]=t;

        t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=,edge[t].flow=,p[y]=t;

    }

    bool bfs()

    {

        memset(d,,sizeof(d));d[S]=;

        int head=,tail=;q[]=S;

        do

        {

            int x=q[++head];

            for (int i=p[x];~i;i=edge[i].nxt)

            if (d[edge[i].to]==-&&edge[i].flow<edge[i].cap)

            {

                d[edge[i].to]=d[x]+;

                q[++tail]=edge[i].to;

            }

        }while (head<tail);

        return ~d[T];

    }

    int work(int k,int f)

    {

        if (k==T) return f;

        int used=;

        for (int i=cur[k];~i;i=edge[i].nxt)

        if (d[k]+==d[edge[i].to])

        {

            int w=work(edge[i].to,min(edge[i].cap-edge[i].flow,f-used));

            edge[i].flow+=w,edge[i^].flow-=w;

            if (edge[i].flow<edge[i].cap) cur[k]=i;

            used+=w;if (used==f) return f;

        }

        if (used==) d[k]=-;

        return used;

    }

    void make(int lim)

    {

        t=-;memset(p,,sizeof(p));

        for (int i=;i<=(k<<);i++) addedge(S,i,);

        for (int i=;i<=l;i++) addedge((k<<)+i,T,w[v[i].x][v[i].y]);

        for (int i=;i<=(k<<);i++)

            for (int j=;j<=l;j++)

            if (dis[i][v[j].x][v[j].y]<=lim) addedge(i,(k<<)+j,);

    }

    int dinic(int lim)

    {

        make(lim);

        ans=;

        while (bfs())

        {

            memcpy(cur,p,sizeof(p));

            ans+=work(S,N);

        }

        return ans;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2547.in","r",stdin);

    freopen("bzoj2547.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),k=read(),l=read();

    for (int i=;i<=(k<<|);i++) u[i].x=read(),u[i].y=read();

    for (int i=;i<=l;i++) v[i].x=read(),v[i].y=read(),w[v[i].x][v[i].y]=read();

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

        a[i][j]=read();

    shortestpath::make();

    for (int i=;i<=(k<<);i++) shortestpath::dijkstra(i);

    int l=,r=k<<,ans;

    while (l<=r)

    {

        int mid=l+r>>;

        if (maxflow::dinic(mid)+mid>=(k<<)) ans=mid,r=mid-;

        else l=mid+;

    }

    cout<<ans;

    return ;

}