#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=1e9+9,inf=1e9+9;
int n,m,en,r,c,o;
struct point
{
	int x,y;
};
point pt[111],ms[11010];
struct observation
{
	int ti,tx,ty;
};
observation ob[111];
struct que
{
	int x,y,ti;
};
que queue[1011000];
int vis[111][111],times,cnt,ans;
int cont[4][111][111];
int dx[]={-1,1,0,0,0};
int dy[]={0,0,-1,1,0};
bool hav[111][111];
void floodfill(int id)
{
	int i,j,s,p,q,ti,tx,ty,temp1,temp2,temp,nx,ny;
	ti=ob[id].ti;
	tx=ob[id].tx;
	ty=ob[id].ty;
	memset(vis,-1,sizeof(vis));
	queue[0].x=tx;
	queue[0].y=ty;
	queue[0].ti=ti;
	times=ti;
	vis[tx][ty]=ti;
	temp1=temp2=0;
	temp=1;
	while(temp1<=temp2)
	{
		times++;
		if(times>=m)
		    break;
		for(i=0;i<r;i++)
		   vis[i][pt[times].y]=times;
        for(i=0;i<c;i++)
           vis[pt[times].x][i]=times;
        for(i=temp1;i<=temp2;i++)
        {
        	for(j=0;j<5;j++)
        	{
	        	nx=queue[i].x+dx[j];
	        	ny=queue[i].y+dy[j];
	        	if(nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]!=times)
	        	{
	        		vis[nx][ny]=times;
	        		queue[temp].x=nx;
	        		queue[temp].y=ny;
	        		queue[temp++].ti=times;
	        	}
	        }
        }
        temp1=temp2+1;
        temp2=temp-1;
	}
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{
			if(hav[i][j])
			   continue;
			for(s=temp1;s<=temp2;s++)
			{
				if(abs(i-queue[s].x)+abs(j-queue[s].y)<=(en-m+1))
				{
					hav[i][j]=true;
					ms[cnt].x=i;
					ms[cnt++].y=j;
					break;
				}
			}
		}
	}
}
void solve()
{
	int i,j,s,p,q,lx,ly,rx,ry;
	memset(cont,0,sizeof(cont));
	for(i=0;i<4;i++)
	{
		for(j=0;j<cnt;j++)
		   cont[i][ms[j].x][ms[j].y]++;
	}
	for(i=0;i<r;i++)
	  for(j=0;j<c;j++)
	  {
  		  if(i>0)
  		     cont[0][i][j]+=cont[0][i-1][j];
	      if(j>0)
	         cont[0][i][j]+=cont[0][i][j-1];
          if(i>0&&j>0)
             cont[0][i][j]-=cont[0][i-1][j-1];
  	  }
    for(i=r-1;i>=0;i--)
       for(j=0;j<c;j++)
       {
       	   if(i<r-1)
       	      cont[1][i][j]+=cont[1][i+1][j];
	       if(j>0)
	          cont[1][i][j]+=cont[1][i][j-1];
           if(i<r-1&&j>0)
              cont[1][i][j]-=cont[1][i+1][j-1];
       }
    for(i=r-1;i>=0;i--)
       for(j=c-1;j>=0;j--)
       {
       	   if(i<r-1)
       	      cont[2][i][j]+=cont[2][i+1][j];
	       if(j<c-1)
	          cont[2][i][j]+=cont[2][i][j+1];
           if(i<r-1&&j<c-1)
              cont[2][i][j]-=cont[2][i+1][j+1];
 	   }
   for(i=0;i<r;i++)
      for(j=c-1;j>=0;j--)
      {
      	  if(i>0)
      	     cont[3][i][j]+=cont[3][i-1][j];
   	      if(j<c-1)
   	         cont[3][i][j]+=cont[3][i][j+1];
          if(i>0&&j<c-1)
             cont[3][i][j]-=cont[3][i-1][j+1];
      }
      for(i=0;i<r;i++)
      {
	    	for(j=0;j<c;j++)
	    	{
	    		if(i==0||j==0||cont[0][i-1][j-1]==0)
	    		{
		    		for(p=i;p<r;p++)
		    		{
			    			for(q=j;q<c;q++)
			    			{
            				   	if(p==r-1||q==c-1||cont[2][p+1][q+1]==0)
            				   	{
	    				           	if(p==r-1||j==0||cont[1][p+1][j-1]==0)
	    				           	{
	            				    	if(i==0||q==c-1||cont[3][i-1][q+1]==0)
	            				    	{
	            				    	   lx=inf;
	            				    	   ly=inf;
	            				    	   rx=-inf;
	            				    	   ry=-inf;
	            				    	   for(s=0;s<cnt;s++)
	            				    	   {
   	    				            		   if(ms[s].x<i||ms[s].x>p)
   	    				            		   { 
   		            				    	   	  if(ly>ms[s].y)
   		            				    	   	    ly=ms[s].y;
            				    	   	          if(ry<ms[s].y)
            				    	   	             ry=ms[s].y;
   		            				    	   }
   		            				    	   if(ms[s].y<j||ms[s].y>q)
   		            				    	   {
   	    				            		   	   if(lx>ms[s].x)
   	    				            		   	      lx=ms[s].x;
 				            		   	           if(rx<ms[s].x)
 				            		   	              rx=ms[s].x;
   	    				            		   }
   	    				            	   }
    				            	       int dx,dy;
    				            	       if(lx==inf)
    				            	          dx=0;
 				            	           else
 				            	              dx=rx-lx;
										   if(ly==inf)
										      dy=0;
							               else
							                  dy=ry-ly;
										   if(ans>dx+q-j)
										      ans=dx+q-j;
										   if(ans>dy+p-i)
										      ans=dy+p-i;	
									   }
	            				   	}
	    				         }
            				 }
			     	}
	    	 	}
	     	}
	   	}
}
int main()
{
	int i,j,s,p,q,id,ti,tx,ty;
	while(scanf("%d%d%d%d%d%d",&n,&m,&en,&r,&c,&o)&&(n!=0||m!=0||en!=0||r!=0||c!=0||o!=0))
	{
		en--;
	//	while(en<0)
	//	   puts("orz");
      //  while(n>=70||m>=100||en>=35000||r>=100||c>=100||r==0||c==0)
      //     puts("orz");
		for(i=0;i<m;i++)
		{
		   scanf("%d%d",&pt[i].x,&pt[i].y);
		   pt[i].x--;
		   pt[i].y--;
		}
		for(i=0;i<n;i++)
           ob[i].ti=-1;
		for(i=0;i<o;i++)
        {
        	scanf("%d",&id);
        	id--;
        	scanf("%d%d%d",&ti,&tx,&ty);
        	tx--;
        	ty--;
        	ti--;
        	while(ti<0)
        	   puts("orz");
			if(ob[id].ti<ti)
        	{
	        	ob[id].ti=ti;
	        	ob[id].tx=tx;
	        	ob[id].ty=ty;
	        } 
        }
        memset(hav,false,sizeof(hav));
        cnt=0;
        for(i=0;i<n;i++)
        {
        	if(ob[i].ti>=0)
            	floodfill(i);
        }
        ans=mod;
        //printf("cnt=%d\n",cnt);
       // for(i=0;i<cnt;i++)
        //   printf("%d %d\n",ms[i].x,ms[i].y);
		solve();
		//while(ans>=mod||ans<=0)
		 //  puts("orz");
        printf("%d\n",ans);
	}
	return 0;
}
/*
1 1 40 100 100 1
50 50
1 1 50 50


*/