#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
typedef pair<int,int> PII;
const int N=1e2+10;
vector<PII> h[N];
int n,m,p;
int dist[N][4010],st[N][4010],vis[15][15][5],sb[15][15],js[N];
void bfs()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<4010;k++)
            {
                int u=(i-1)*m+j;
                dist[u][k]=INF;
            }
        }
    }
    queue<PII> q;
    dist[1][js[1]]=0;
    q.push({1,js[1]});

    while(q.size())
    {
        auto it=q.front();
        q.pop();
        if(st[it.fi][it.se]) continue;
        st[it.fi][it.se]=1;
        for(auto t:h[it.fi])
        {

            int w=t.se;
            if(w!=p+1){
                if(((it.se>>w)&1)==0)
                {
                    continue;
                }
            }
            if(st[t.fi][it.se|js[t.fi]]) continue;
            if(dist[t.fi][it.se|js[t.fi]]>dist[it.fi][it.se]+1)
            {
                dist[t.fi][it.se|js[t.fi]]=dist[it.fi][it.se]+1;
                if(st[t.fi][it.se|js[t.fi]]==0)
                {
                    q.push({t.fi,it.se|js[t.fi]});
                }
            }
        }
    }
}
void solve(){
    cin>>n>>m>>p;
    int k;
    cin>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=4;k++)
            {
                vis[i][j][k]=p+1;
            }
        }
    }
    for(int j=1;j<=m;j++) vis[1][j][1]=0,vis[n][j][4]=0;
    for(int i=1;i<=n;i++) vis[i][1][2]=0,vis[i][m][3]=0;
    for(int i=1;i<=k;i++)
    {
        int a,b,c,d,op;
        cin>>a>>b>>c>>d>>op;
        if(a!=c)
        {
            if(a>c)
            {
                vis[a][b][1]=op;
                vis[c][d][4]=op;
            }else{
                vis[a][b][4]=op;
                vis[c][d][1]=op;

            }
        }else if(b!=d)
        {
            if(b>d)
            {
                vis[a][b][2]=op;
                vis[c][d][3]=op;
            }else{
                vis[a][b][3]=op;
                vis[c][d][2]=op;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int u=(i-1)*m+j;
            for(int k=1;k<=4;k++)
            {
                int v;
                if(k==1) v=(i-2)*m+j;
                if(k==2) v=(i-1)*m+j-1;
                if(k==3) v=(i-1)*m+j+1;
                if(k==4) v=(i)*m+j;
                if(vis[i][j][k]!=0)
                {
                    if(vis[i][j][k]==p+1) h[u].push_back({v,p+1});
                    else h[u].push_back({v,vis[i][j][k]});
                }
            }
        }
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y,op;cin>>x>>y>>op;
        js[(x-1)*m+y]|=(1<<op);
    }   
    bfs();
    int ans=INF;
    for(int i=0;i<4010;i++)
    {
        ans=min(ans,dist[n*m][i]);
    }
    if(ans>1e15)cout<<-1<<endl;
    else cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    T=1;
    while(T--)solve();
    return 0;
}