AOJ0274.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(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);

    while(f > 0) {
      typedef pair<int, int> Pi;
      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;
  }
};

int D, K, L, M, N, P;
int c[8][8];
int r[200][8], t[200][8];

int rbit[200], tbit[200]; // 1部品ごとに2bit。00なら0個/01なら1個/10なら2個
int dp[1<<16]; // i回目の授業でj個買った時に部品の集合をkにする最小価格
// 最後の授業までに部品が揃っていれば課題を完成できるので、i回目の情報は使い回せる

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

  while(cin >> D >> K >> L, D || K || L) {
    rep(i, D) rep(j, K) cin >> c[i][j];
    cin >> M >> N >> P;
    rep(i, M) rep(j, K) cin >> r[i][j];
    rep(i, P) rep(j, K) cin >> t[i][j];

    rep(i, M) {
      rbit[i] = 0;
      rep(j, K) rbit[i] |= r[i][j]<<(j*2);
    }
    rep(i, P) {
      tbit[i] = 0;
      rep(j, K) tbit[i] |= t[i][j]<<(j*2);
    }

    fill(dp, dp + (1<<16), inf);
    dp[0] = 0;
    rep(i, D) rep(j, L) { // L回繰り返せば1日にL個まで買ったことになる
      for(int k = (1<<K*2)-1; k >= 0; k--) { // 1個ずつ買いたいのでこの向き
	rep(l, K) if(((k>>(l*2))&3) < 2) { // 01なら1個、10なら2個持ってる
	  dp[k+(1<<(l*2))] = min(dp[k+(1<<(l*2))], dp[k] + c[i][l]);
	}
      }
    }

    int s = M + P, t = s + 1, V = t + 1;
    PrimalDual graph(V);
    rep(i, M) {
      graph.add_edge(s, i, 1, 0); // 課題は全員異なるから容量1
      if(dp[rbit[i]] != inf) graph.add_edge(i, t, 1, dp[rbit[i]]); // 袋なしで作る
    }
    rep(i, M) rep(j, P) {
      bool flag = true;
      rep(k, K) if(((rbit[i]>>(k*2))&3) < ((tbit[j]>>(k*2))&3)) flag = false; // 袋の中身は全部使わないといけない
      if(flag && dp[rbit[i]-tbit[j]] != inf) graph.add_edge(i, M + j, 1, dp[rbit[i]-tbit[j]]);
    }
    rep(i, P) {
      graph.add_edge(M + i, t, 1, 0); // 袋は全員異なるから容量1
    }
    cout << graph.min_cost_flow(s, t, N) << endl;
  }

  return 0;
}