AOJ0293.cpp

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

// Sccessive Shortest Path(Primal Dual): minimum cost maximum flow
struct PrimalDual
{
  struct edge
  {
    int to, capacity, cost, rev;
    edge(){}
    edge(int to, int capacity, int cost, int rev):to(to), capacity(capacity), cost(cost), rev(rev){}
  };

  vector< vector<edge> > graph;
  vector<int> potential, mincost, prevv, preve;
  PrimalDual(){}
  PrimalDual(int V):graph(V), potential(V), mincost(V), prevv(V), preve(V){}
  void add_edge(int from, int to, int capacity, int cost)
  {
    graph[from].push_back(edge(to, capacity, cost, (int)graph[to].size()));
    graph[to].push_back(edge(from, 0, -cost, (int)graph[from].size()-1));
  }
  int min_cost_flow(int source, int sink, int f)
  {
    int res = 0;
    fill(potential.begin(), potential.end(), 0);
    fill(prevv.begin(), prevv.end(), -1);
    fill(preve.begin(), preve.end(), -1);

    typedef pair<int, int> Pi;
    while(f > 0) {
      priority_queue<Pi, vector<Pi>, greater<Pi> > que;
      fill(mincost.begin(), mincost.end(), inf);
      mincost[source] = 0;
      que.push(Pi(0, source));
      while(!que.empty()) {
	Pi p = que.top(); que.pop();
	int v = p.second;
	if(mincost[v] < p.first) continue;
	for(int i = 0; i < (int)graph[v].size(); i++) {
	  edge& e = graph[v][i];
	  int dual_cost = mincost[v] + e.cost + potential[v] - potential[e.to];
	  if(e.capacity > 0 && dual_cost < mincost[e.to]) {
	    mincost[e.to] = dual_cost;
	    prevv[e.to] = v; preve[e.to] = i;
	    que.push(Pi(mincost[e.to], e.to));
	  }
	}
      }

      if(mincost[sink] == inf) return -1;
      for(int v = 0; v < (int)graph.size(); v++) potential[v] += mincost[v];
      int d = f;
      for(int v = sink; v != source; v = prevv[v]) d = min(d, graph[prevv[v]][preve[v]].capacity);
      f -= d;
      res += d * potential[sink];
      for(int v = sink; v != source; v = prevv[v]) {
	edge& e = graph[prevv[v]][preve[v]];
	e.capacity -= d;
	graph[v][e.rev].capacity += d;
      }
    }
    return res;
  }
};


#define MAX_N 100
#define MAX_M 5

int N, M, B;
int ax[MAX_N], ay[MAX_N];
int bx[MAX_M], by[MAX_M], c[MAX_M], f[MAX_M];

int S, T, V;
PrimalDual graph;

void build(int bit, int D) {
  graph = PrimalDual(V);
  rep(i, N) graph.add_edge(S, i, 1, 0);
  rep(i, M) if((bit>>i)&1) {
    rep(j, N) graph.add_edge(j, N + i, 1, max(0LL, abs(ax[j]-bx[i]) + abs(ay[j]-by[i]) - D));
  }
  rep(i, M) if((bit>>i)&1) graph.add_edge(N + i, T, c[i], 0);
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(cin >> N >> M >> B, N || M || B) {
    rep(i, N) cin >> ax[i] >> ay[i];
    rep(i, M) cin >> bx[i] >> by[i] >> c[i] >> f[i];

    S = N + M, T = S + 1, V = T + 1;
    int ans = inf;
    rep(bit, 1<<M) {
      int res = 0, num = 0;
      rep(i, M) if((bit>>i)&1) res += f[i], num++;
      int lb = 0, ub = 5000;
      bool flag = false;
      while(lb + 1 < ub) {
	int D = (lb + ub) / 2;
	build(bit, D);
	int F = graph.min_cost_flow(S, T, N) + D*B*num;
	build(bit, D-1);
	int G = graph.min_cost_flow(S, T, N) + (D-1)*B*num;
	if(F == -1 || G == -1) {
	  flag = true;
	  break;
	}
	if(F < G) lb = D;
	else ub = D;
      }
      if(flag) continue;
      build(bit, lb);
      res += graph.min_cost_flow(S, T, N) + lb*B*num;
      ans = min(ans, res);

    }
    cout << ans << endl;
  }

  return 0;
}