#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1607"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
template<typename V>
V compress(V v){
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  return v;
}
template<typename T>
map<T, int> dict(const vector<T> &v){
  map<T, int> res;
  for(int i=0;i<(int)v.size();i++)
    res[v[i]]=i;
  return res;
}
map<char, int> dict(const string &v){
  return dict(vector<char>(v.begin(),v.end()));
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed ABC036_C(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  auto v=compress(a);
  auto m=dict(v);
  for(int i=0;i<n;i++) cout<<m[a[i]]<<endl;
  return 0;
}
/*
  verified on 2018/08/26
  https://abc036.contest.atcoder.jp/tasks/abc036_c
*/

signed main(){
  ABC036_C();
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template <typename T>
using gtree = tree<T,null_type,less<T>,rb_tree_tag,
                   tree_order_statistics_node_update>;
// usage:
// find_by_order(int k):
// return the iterator of k-th smallest element (0-indexed)
// order_of_key(T key):  return the index of key in tree
//END CUT HERE
#ifndef call_from_test
signed ARC028_B(){
  using ll = long long;
  int n,k;
  cin>>n>>k;
  vector<int> xs(n);
  for(int i=0;i<n;i++) cin>>xs[i];
  map<int, int> mp;
  for(int i=0;i<n;i++) mp[xs[i]]=i+1;
  gtree<ll> G;
  for(int i=0;i<k-1;i++) G.insert(xs[i]);
  for(int i=k-1;i<n;i++){
    G.insert(xs[i]);
    auto key=*G.find_by_order(k-1);
    cout<<mp[key]<<endl;
  }
  return 0;
}

/*
  verified on 2019/12/09
  https://atcoder.jp/contests/arc028/tasks/arc028_2
*/

signed ARC033_C(){
  int q;
  cin>>q;
  gtree<int> G;
  while(q--){
    int t,x;
    cin>>t>>x;
    if(t==1) G.insert(x);
    if(t==2){
      int k=*G.find_by_order(x-1);
      G.erase(k);
      cout<<k<<endl;
    }
  }
  return 0;
}

/*
  verified on 2019/12/09
  https://atcoder.jp/contests/arc033/tasks/arc033_3
*/

signed main(){
  //ARC028_B();
  //ARC033_C();
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#endif
//BEGIN CUT HERE
// prohibited to push an element less than popped one
// Key: int or long long
template<typename K,typename V>
struct RadixHeap{
  static constexpr int bit = sizeof(K) * 8;
  array<vector< pair<K, V> >, bit> vs;

  int size;
  K last;
  RadixHeap():size(0),last(0){}

  bool empty() const{return size==0;}

  inline int getbit(int a){
    return a?bit-__builtin_clz(a):0;
  }

  inline int getbit(long long a){
    return a?bit-__builtin_clzll(a):0;
  }

  void emplace(K key,V val){
    size++;
    vs[getbit(key^last)].emplace_back(key,val);
  }

  pair<K, V> pop(){
    if(vs[0].empty()){
      int idx=1;
      while(vs[idx].empty()) idx++;
      last=min_element(vs[idx].begin(),vs[idx].end())->first;
      for(auto &p:vs[idx]) vs[getbit(p.first^last)].emplace_back(p);
      vs[idx].clear();
    }
    --size;
    auto res=vs[0].back();
    vs[0].pop_back();
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#undef call_from_test

const int BS = 8, BS2 = BS * 2;
const int msk = (1<<BS)-1;
const int MAX = 12 * (1<<BS) * (1<<BS);
int dist[MAX];
bool hole[MAX];
long long add[(1<<BS) * (1<<BS)];
long long dp[(1<<BS)][(1<<BS)];

signed main(){
  int n;
  while(cin>>n,n){
    int m,k,r;
    cin>>m>>k>>r;
    vector<int> x(n),y(n),z(n);
    for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>z[i];
    vector<int> u1(m),v1(m),u2(m),v2(m),w(m);
    for(int i=0;i<m;i++) cin>>u1[i]>>v1[i]>>u2[i]>>v2[i]>>w[i];

    vector<int> vx(x),vy(y);
    for(int p=0;p<m;p++){
      vx.emplace_back(u1[p]);
      vx.emplace_back(u2[p]);
      vy.emplace_back(v1[p]);
      vy.emplace_back(v2[p]);
      if(w[p]!=k) continue;
      if(u1[p]-1>=1) vx.emplace_back(u1[p]-1);
      if(u2[p]+1<=r) vx.emplace_back(u2[p]+1);
      if(v1[p]-1>=1) vy.emplace_back(v1[p]-1);
      if(v2[p]+1<=r) vy.emplace_back(v2[p]+1);
    }

    vx=compress(vx);
    vy=compress(vy);
    auto mx=dict(vx);
    auto my=dict(vy);

    // kokokara y yuusen
    auto idx=[&](int cy,int cx,int f){return (f<<BS2)|(cy<<BS)|cx;};

    memset(hole,0,sizeof(hole));
    for(int p=0;p<m;p++)
      for(int i=my[v1[p]];i<=my[v2[p]];i++)
        for(int j=mx[u1[p]];j<=mx[u2[p]];j++)
          hole[idx(i,j,w[p])]=1;

    int sy=vy.size(),sx=vx.size();

    auto dijkstra=
      [&](int a)->void{
        vector<int> wy,wx;
        for(int p=0;p<m;p++){
          if(w[p]<=z[a]) continue;
          wy.emplace_back(v1[p]);
          wy.emplace_back(v2[p]);
          wx.emplace_back(u1[p]);
          wx.emplace_back(u2[p]);
        }
        wy.emplace_back(y[a]);
        wx.emplace_back(x[a]);
        wy=compress(wy);
        wx=compress(wx);
        auto zy=dict(wy);
        auto zx=dict(wx);
        int ty=zy.size(),tx=zx.size();

        vector<pair<int, int> > vs;
        {
          for(int i=0;i<MAX;i++) dist[i]=INT_MAX;
          RadixHeap<int, int> q;
          {
            int v=idx(zy[y[a]],zx[x[a]],z[a]);
            dist[v]=0;
            q.emplace(dist[v],v);
          }

          while(!q.empty()){
            auto p=q.pop();
            int v=p.second;
            if(dist[v]<p.first) continue;

            int f=v>>BS2,i=(v>>BS)&msk,j=v&msk;
            int ai=my[wy[i]],aj=mx[wx[j]];
            if(f==k){
              vs.emplace_back((ai<<BS)|aj,dist[v]);
              continue;
            }

            auto push=
              [&](int ni,int nj,int nf){
                int u=idx(ni,nj,nf);
                int c=abs(wy[ni]-wy[i])+abs(wx[nj]-wx[j]);

                if(dist[u]>dist[v]+c){
                  dist[u]=dist[v]+c;
                  q.emplace(dist[u],u);
                }
              };

            if(hole[idx(ai,aj,f+1)]){
              push(i,j,f+1);
              continue;
            }

            if(i+1<ty) push(i+1,j,f);
            if(i-1>=0) push(i-1,j,f);
            if(j+1<tx) push(i,j+1,f);
            if(j-1>=0) push(i,j-1,f);
          }
        }
        {
          for(int i=0;i<(sy<<BS);i++) add[i]=INT_MAX;
          RadixHeap<int, int> q;
          for(auto p:vs){
            int v=p.first,d=p.second;
            add[v]=d;
            q.emplace(add[v],v);
          }

          while(!q.empty()){
            auto p=q.pop();
            int v=p.second;
            if(add[v]<p.first) continue;

            int i=v>>BS,j=v&msk;
            auto push=
              [&](int ni,int nj){
                int u=(ni<<BS)|nj;
                int c=abs(vy[ni]-vy[i])+abs(vx[nj]-vx[j]);
                if(add[u]>add[v]+c){
                  add[u]=add[v]+c;
                  q.emplace(add[u],u);
                }
              };

            if(i+1<sy) push(i+1,j);
            if(i-1>=0) push(i-1,j);
            if(j+1<sx) push(i,j+1);
            if(j-1>=0) push(i,j-1);
          }
        }
      };

    memset(dp,0,sizeof(dp));
    for(int p=0;p<n;p++){
      dijkstra(p);
      for(int i=0;i<sy;i++)
        for(int j=0;j<sx;j++)
          dp[i][j]+=add[(i<<BS)|j];
    }

    long long ans=1e18;
    for(int i=0;i<sy;i++)
      for(int j=0;j<sx;j++)
        if(!hole[idx(i,j,k)]) chmin(ans,dp[i][j]);

    for(int p=0;p<n;p++) ans+=(k-z[p])*100;
    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 7976