#include <stdio.h>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <deque>
#include <tuple>
#include <cstring>
#include <functional>
#include <queue>


using namespace std;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())

typedef pair<int, int> Pii;
using namespace std;


struct Edge {
	int cap, to, cost, rev;
	Edge(){}
	Edge(int c, int t, int st, int r) : cap(c), to(t), cost(st), rev(r) {}
};

void addEdge(vector<vector<Edge>>& g, int from, int to, int cap, int cost){
	g[from].push_back(Edge(cap, to, cost, g[to].size()));
	g[to].push_back(Edge(0, from, -cost, g[from].size() - 1)); //rev edge
}


// O(VE+FElogV)
int minCostFlow(vector<vector<Edge>> &g, int s, int t, int f, bool negative = false){
	typedef pair<int, int> P;
	const int n = g.size();
	int res = 0;
	vector<int> h(n), prevv(n), preve(n);
	const int inf = 10000000; //check

	if (negative) {
		h.assign(n, inf);
		h[s] = 0;

		bool update = true;
		while (update) {
			update = false;
			for (int v = 0; v < n; v++) {
				if (h[v] == inf) continue;
				for (int i = 0; i < sz(g[v]); i++) {
					auto &e = g[v][i];
					if (e.cap > 0 && h[e.to] > h[v] + e.cost) {
						h[e.to] = h[v] + e.cost;
						prevv[e.to] = v; preve[e.to] = i;
						update = true;
					}
				}
			}
		}
	}

	while (f > 0) {
		//????????????????????§????????????(cost = ???????????¨)
		priority_queue<P, vector<P>, greater<P> > que;
		vector<int> dist(n, inf);
		dist[s] = 0;
		que.push(P(0, s));

		while (!que.empty()) {
			P p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first) continue;
			if (v == t) break;
			for (int i = 0; i < sz(g[v]); i++) {
				auto &e = g[v][i];
				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;  preve[e.to] = i;
					que.push(P(dist[e.to], e.to));
				}
			}
		}

		if (dist[t] == inf) return -1; //??????????????????
		FOR(v, n) h[v] += dist[v];

		int d = f;
		for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);

		f -= d;//?????????????????????
		res += d * h[t]; //???????????????????????????????¨?????????????

		//??????????¨????
		for (int v = t; v != s; v = prevv[v]) {
			auto &e = g[prevv[v]][preve[v]];
			e.cap -= d; g[v][e.rev].cap += d;
		}
	}
	return res;
}

int popcount(long long x){
	x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
	x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
	x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);
	return (int)(x * 0x0101010101010101ULL >> 56);
}

struct P {
	int x, y, c, f;
};
int main() {
	int N, M, B;
	while (scanf("%d%d%d",&N,&M,&B) && N) {
		vector<P> people(N);
		for (int i = 0; i < N; i++) scanf("%d%d", &people[i].x, &people[i].y);
		vector<P> place(M);
		for (int i = 0; i < M; i++) scanf("%d%d%d%d", &place[i].x, &place[i].y, &place[i].c, &place[i].f);
		vector<vector<Edge>> g(N + M + 2);
		auto f = [&](int D, int bit) {
			if (D < 0) return (int)1e9;
			int ans = 1e9;
			int sum = 0;
			int cnt = 0;
			for (int i = 0; i < M; i++) {
				if (bit >> i & 1) {
					sum += place[i].c;
					cnt += place[i].f;
				}
			}
			FOR(i, sz(g)) g[i].clear();
			int s = g.size() - 1;
			int t = g.size() - 2;
			for (int i = 0; i < N; i++)
				addEdge(g, s, i, 1, 0);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if ((bit >> j & 1) == 0)continue;
					int dist = max(0, abs(people[i].x - place[j].x) + abs(people[i].y - place[j].y) - D);
					addEdge(g, i, N + j, 1, dist);
				}
			}
			for (int i = 0; i < M; i++) {
				addEdge(g, N + i, t, place[i].c, 0);
			}

			int res = minCostFlow(g, s, t, N);
			if (res != -1) ans = min(ans, res + cnt + popcount(bit)*D*B);
			return ans;
		};

		int ans = 1e9;

		for (int bit = 0; bit < (1 << M); bit++) {
			int l = 0, r = 4001;
			while (r - l > 2) {
				int a = (2 * l + r) / 3;
				int b = (l + 2 * r) / 3;
				if (f(a, bit) > f(b, bit)) {
					l = a;
				} else {
					r = b;
				}
			}
			for (int i = l; i < r; i++) ans = min(ans, f(i, bit));
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1244