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

const int MAX_N = 100;
const int MAX_M = 5;
const int MAX_V = MAX_N + MAX_M + 2;
const int MAX_D = 4181;
const int FIBONACCI = 20;

const int INF = 1000000000;
const int NIL = -1;

struct Home {int x, y;};
struct Hall {int x, y, c, f;};

int N, M, B;
Home home[MAX_N];
Hall hall[MAX_M];

int Fibonacci[FIBONACCI];
unordered_map<int, int> memo;

int V;
int source, sink;
int weight[MAX_V][MAX_V];
int capacity[MAX_V][MAX_V];
int flow[MAX_V][MAX_V];
int potential[MAX_V];
int d[MAX_V];
int p[MAX_V];

struct Node {
  int w, c, p;
  bool operator<(const Node& n) const {return w > n.w;}
};
priority_queue<Node> q;

int init1d[MAX_V];
int init2d[MAX_V][MAX_V];
int NIL1d[MAX_V];
int INF1d[MAX_V];

int answer;

int residue(int from, int to) {return capacity[from][to] - flow[from][to];}
int relative_weight(int from, int to) {return weight[from][to] + potential[from] - potential[to];}

// ???????????????????°??????¨???
int PrimalDual() {
  int result = 0;
  memcpy(potential, init1d, sizeof(potential));
  memcpy(flow, init2d, sizeof(flow));
  while(true) {
    // Dijkstra O(E * V * log V)
    memcpy(d, INF1d, sizeof(d));
    memcpy(p, NIL1d, sizeof(p));
    q.push({0, source, NIL});
    while(!q.empty()) {
      auto node = q.top();
      q.pop();
      if(d[node.c] != INF) continue;
      d[node.c] = node.w;
      p[node.c] = node.p;
      if(node.c < N) {
          for(int to = N; to < N + M; ++to) if(0 < residue(node.c, to)) if(node.w + relative_weight(node.c, to) < d[to]) q.push({node.w + relative_weight(node.c, to), to, node.c});
      } else if(node.c < N + M) {
          for(int to = 0; to < N; ++to) if(0 < residue(node.c, to)) if(node.w + relative_weight(node.c, to) < d[to]) q.push({node.w + relative_weight(node.c, to), to, node.c});
          if(0 < residue(node.c, sink)) if(node.w + relative_weight(node.c, sink) < d[sink]) q.push({node.w + relative_weight(node.c, sink), sink, node.c});
      } else if(node.c == source) {
          for(int to = 0; to < N; ++to) if(0 < residue(node.c, to)) if(node.w + relative_weight(node.c, to) < d[to]) q.push({node.w + relative_weight(node.c, to), to, node.c});
      }
    }
    if(p[sink] == NIL) break;
    for(int i = 0; i < V; ++i) potential[i] += d[i];
    for(int v = sink; p[v] != NIL; v = p[v]) {
      ++flow[p[v]][v];
      --flow[v][p[v]];
      result += weight[p[v]][v];
    }
    if(answer <= result) return INF;
  }
  return result;
}

// ?§?????£???????
int allowance(int from, int to, int D) {
  return max(abs(hall[to].x - home[from].x) + abs(hall[to].y - home[from].y) - D, 0);
}

// ??????
int cost(int bit, int D) {
  int result = 0;
  memcpy(capacity, init2d, sizeof(capacity));
  memcpy(weight, init2d, sizeof(weight));
  for(int i = 0; i < N; ++i) {
    capacity[source][i] = 1;
  }
  for(int i = 0; i < M; ++i) if((bit >> i) & 1) {
    capacity[N + i][sink] = hall[i].c;
    result += hall[i].f;
    result += D * B;
  }
  if(result >= answer) return INF;
  for(int i = 0; i < N; ++i) for(int j = 0; j < M; ++j) if((bit >> j) & 1) {
    capacity[i][N + j] = 1;
    weight[i][N + j] = allowance(i, j, D);
    weight[N + j][i] = -weight[i][N + j];
  }
  result += PrimalDual();
  return result;
};

int solve() {
  answer = INF;
  // ?????´?????¨??¢?´¢
  for(int bit = 1; bit < (1 << M); ++bit) {
    int total_capacity = 0;
    int total_fee = 0;
    for(int i = 0; i < M; ++i) if((bit >> i) & 1) {
      total_capacity += hall[i].c;
      total_fee += hall[i].f;
    }
    if(total_capacity < N) continue;
    if(answer <= total_fee) continue;
    // ?????¢???????????¢?´¢
    memo.clear();
    int low = 0;
    int high = Fibonacci[FIBONACCI - 1];
    for(int i = FIBONACCI - 1; 1 < i; --i) {
      int left = low + Fibonacci[i - 2];
      int right = high - Fibonacci[i - 2];
      int f_left = (memo.count(left) ? memo[left] : memo[left] = cost(bit, left));
      int f_right = (memo.count(right) ? memo[right] : memo[right] = cost(bit, right));
      (f_left > f_right) ? (low = left) : (high = right);
    }
    answer = min({answer, memo[low], memo[high]});
  }
  return answer;
}

int main() {
  Fibonacci[0] = 0;
  Fibonacci[1] = 1;
  for(int i = 2; i < FIBONACCI; ++i) Fibonacci[i] = Fibonacci[i - 1] + Fibonacci[i - 2];

  for(int i = 0; i < MAX_V; ++i) {
    INF1d[i] = INF;
    NIL1d[i] = NIL;
  }

  while(cin >> N >> M >> B, N | M | B) {
    for(int i = 0; i < N; ++i) cin >> home[i].x >> home[i].y;
    for(int i = 0; i < M; ++i) cin >> hall[i].x >> hall[i].y >> hall[i].c >> hall[i].f;
    V = N + M + 2;
    source = N + M;
    sink = N + M + 1;
    cout << solve() << endl;
  }
}

Measured memory_bytes: 1388