Problem: Izua University Elementary School is famous as one of Japan's leading competition programmer training schools. The teachers at this school have a wide range of algorithmic knowledge and utilize it on a daily basis. As a teacher, you will be in charge of drawing and crafting classes this year. In this class, all children are supposed to complete one task in one year. The outline of the class is as follows.

* There are D lessons in a year (no lessons more than once on the same day), all of which are devoted to assignment production.
* There are M types of assignments to create.
* Assign one task from M types to each child.
* There are N children, and each of them is assigned a different task.



Children use several of the K types of parts to complete the task. The outline of the assignment production is as follows.

* The type and number of parts to be used are predetermined for each task.
* The type and number of parts used to complete the task must match the type and number of parts used in the task in just proportion.
* For different tasks, the types and numbers of parts used may all be the same.
* For each task, only two parts of the same type can be used.
* The order in which the parts are used does not affect the completion of the task.
* P bags containing some parts are prepared in advance. However, different bags may contain the same type and number of parts.
* Teachers can only give one bag per child (some children may not give it).
* The same bag cannot be given to two or more children (on the contrary, some bags may not be given to anyone).
* The child who is given the bag must use all the parts contained in the bag for the tasks he / she creates.



Parts used for the assignment other than the parts in the bag must be purchased separately. The conditions for purchasing parts are as follows.

* Parts can only be purchased on class days and can only be used on that day.
* Up to L parts can be purchased in one lesson for each task.
* Prices are set according to the type of parts, and the price fluctuates depending on the date of purchase. However, none of them will be out of stock.



Under these conditions, you want to keep your lesson costs as low as possible. Therefore, I decided to create a program to calculate the minimum total cost of purchasing parts for all children.



input

The input consists of multiple datasets. The end of the input is indicated by three zero lines. Each dataset is given in the following format:


D K L
c1,1 c1,2 ... c1, K
c2,1 c2,2 ... c2, K
::
cD, 1 cD, 2 ... cD, K
M N P
r1,1 r1,2 ... r1, K
r2,1 r2,2 ... r2, K
::
rM, 1 rM, 2 ... rM, K
t1,1 t1,2 ... t1, K
t2,1 t2,2 ... t2, K
::
tP, 1 tP, 2 ... tP, K


The numbers given on each line are separated by a single space.

D (1 ≤ D ≤ 8) indicates the number of lessons, K (1 ≤ K ≤ 8) indicates the number of parts types, and L (1 ≤ L ≤ 8) indicates the number of parts that can be purchased per day. .. cd, k (1 ≤ cd, k ≤ 100) indicates the price of part k on day d.

M (1 ≤ M ≤ 200) indicates the number of task types, N (1 ≤ N ≤ M) indicates the number of students, and P (1 ≤ P ≤ 200) indicates the number of bags.

rm, k (0 ≤ rm, k ≤ 2) indicates the number of parts k required for task m, and tp, k (0 ≤ tp, k ≤ 2) indicates the number of parts k contained in the bag p.

Tasks that do not require any parts or empty bags shall not be given.

The number of datasets does not exceed 20.

output

For each data set, output the minimum value of the total parts purchase cost for all students on one line. If N kinds of works cannot be completed, -1 is output.

Example

Input

2 2 1
5 3
2 2
3 3 1
2 0
1 2
2 2
1 1
2 2 1
5 3
2 2
3 2 1
2 0
1 2
2 2
1 1
2 2 2
5 3
2 2
3 2 1
2 0
1 2
2 2
1 1
4 3 1
2 2 1
3 2 2
2 3 3
1 2 2
5 4 3
1 1 0
1 0 1
1 0 2
1 1 2
2 2 2
1 0 1
2 0 2
1 1 1
0 0 0


Output

-1
9
6
7

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

typedef int Weight;
struct Edge {
  int src, dst;
  Weight capacity, cost;
  int rev;
  Edge(int src, int dst, Weight capacity, Weight cost) :
    src(src), dst(dst), capacity(capacity), cost(cost) { }
  Edge(int src, int dst, Weight capacity, Weight cost, int rev) :
    src(src), dst(dst), capacity(capacity), cost(cost), rev(rev) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.cost != f.cost ? e.cost > f.cost : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int s, int d, Weight cap, Weight cost) {
  g[s].push_back(Edge(s,d,cap,cost));
  g[d].push_back(Edge(d,s,0,-cost));
}

#define RESIDUE(u,v) (capacity[u][v] - flow[u][v])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])

// Dijkstra
pair<Weight, Weight> minimumCostFlow(const Graph &g, int s, int t) {
  const int n = g.size();
  Matrix capacity(n, Array(n)), cost(n, Array(n)), flow(n, Array(n));
  REP(u,n) FOR(e,g[u]) {
    capacity[e->src][e->dst] += e->capacity;
    cost[e->src][e->dst] += e->cost;
  }
  pair<Weight, Weight> total; // (cost, flow)
  vector<Weight> h(n, INF);
  h[s] = 0;
  // ベルマンフォードでポテンシャルを求めて負辺に対応
  REP(k, n) REP(i, n) FOR(e,g[i]) if (capacity[e->src][e->dst])
    h[e->dst] = min(h[e->dst], h[e->src] + cost[e->src][e->dst]);

  for (Weight F = INF; F > 0; ) { // residual flow
    vector<Weight> d(n, INF); d[s] = 0;
    vector<int> p(n, -1);
    priority_queue<Edge> Q;
    for (Q.push(Edge(-2, s, 0, 0)); !Q.empty(); ) {
      Edge e = Q.top(); Q.pop();
      if (p[e.dst] != -1) continue;
      p[e.dst] = e.src;
      FOR(f, g[e.dst]) if (RESIDUE(f->src, f->dst) > 0) {
        if (d[f->dst] > d[f->src] + RCOST(f->src, f->dst)) {
          d[f->dst] = d[f->src] + RCOST(f->src, f->dst);
          Q.push( Edge(f->src, f->dst, 0, d[f->dst]) );
        }
      }
    }
    if (p[t] == -1) break;
    Weight f = F;
    for (int u = t; u != s; u = p[u])
      f = min(f, RESIDUE(p[u], u));
    for (int u = t; u != s; u = p[u]) {
      total.first += f * cost[p[u]][u];
      flow[p[u]][u] += f; flow[u][p[u]] -= f;
    }
    F -= f;
    total.second += f;
    REP(u, n) if (h[u] != INF) h[u] += d[u]; // ifいらない？
  }
  // REP(i,n) {
  //   REP(j,n) {
  //     if (i < 5 && j >= 5 && j < 5+3) {
  //       if (flow[i][j]) {
  //         cout << tpl("*",i,j-5,flow[i][j]) << endl;
  //       }
  //     }
  //   }
  // }
  return total;
}

template<int N, int M>
struct Pow {
  ll a[M+1];
  Pow() { a[0] = 1; REP(i,M) a[i+1] = a[i]*N; }
  int get(ll S, int i) { return S/a[i]%N; }
  ll change(ll S, int i, int x) { S -= get(S,i)*a[i]; S += x*a[i]; return S; }
  bool can_merge(ll S, ll T) {
    REP(i,M) if (get(S,i) + get(T,i) >= N) return 0;
    return 1;
  }
  bool can_sub(ll S, ll T) {
    REP(i,M) if (get(S,i) < get(T,i)) return 0;
    return 1;
  }
  ll sub(ll S, ll T) {
    REP(i,M) S = change(S,i,max(0,get(S,i)-get(T,i)));
    return S;
  }
  int popcount(ll S) {
    int res = 0;
    REP(i,M) res += get(S,i);
    return res;
  }
  string getString(ll S) {
    stringstream ss;
    REP(i,M) ss << get(S,i);
    return ss.str();
  }
};
Pow<3,8> pw3;

int dp[9][6600];
int c[8][8];
vector<int> V[6600];
int D,K,L;

void dfs(int S, int T, int idx, int num) {
  if (idx == K) {
    V[S].push_back(T);
    return;
  }
  REP(i,3-pw3.get(S,idx)) {
    if (num + i > L) break;
    dfs(S,pw3.change(T,idx,i), idx+1, num+i);
  }
}

int work[200];
int bag[200];

int main() {
  while(input(D,K,L), D) {
    REP(i,D) inputs(c[i],K);

    REP(i,6600) V[i].clear();
    int fuga = 0;
    REP(S,pw3.a[K]) {
      dfs(S,0,0,0);
      fuga += V[S].size();
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;
    REP(i,D) {
      vector<int> cc(pw3.a[K]);
      REP(S,pw3.a[K]) {
        REP(j,K) {
          cc[S] += pw3.get(S,j) * c[i][j];
        }
      }
      REP(S,pw3.a[K]) {
        for (int T : V[S]) {
          chmin(dp[i+1][S+T], dp[i][S] + cc[T]);
        }
      }
    }
    // REP(S,pw3.a[K]) {
    //   cout << pw3.getString(S) << " " << dp[D][S] << endl;
    // }
    int M, N, P;
    input(M,N,P);
    REP(i,M) {
      int S = 0;
      REP(j,K) {
        int r;
        input(r);
        S = pw3.change(S,j,r);
      }
      work[i] = S;
    }
    REP(i,P) {
      int S = 0;
      REP(j,K) {
        int r;
        input(r);
        S = pw3.change(S,j,r);
      }
      bag[i] = S;
    }
    Graph g(M+P+4);
    REP(i,M) {
      REP(j,P) {
        if (!pw3.can_sub(work[i], bag[j])) continue;
        int cost = dp[D][pw3.sub(work[i], bag[j])];
        if (cost != INF) {
          add_edge(g, i, M+j, 1, cost);
          // cout << tpl(i,j,cost) << endl;
        }
      }
      int cost = dp[D][work[i]];
      if (cost != INF) {
        // cout << tpl("!", i, cost) << endl;
        add_edge(g, i, M+P+1, 1, cost);
      }
    }
    REP(i,M) add_edge(g, M+P, i, 1, 0);
    REP(j,P) add_edge(g, M+j, M+P+1, 1, 0);
    add_edge(g, M+P+2, M+P, N, 0);
    auto res = minimumCostFlow(g, M+P+2, M+P+1);
    if (res.second == N) cout << res.first << endl;
    else cout << -1 << endl;

  }
}