Arts and Crafts

Time Limit : 8 sec, Memory Limit : 65536 KB

図画工作

イヅア大学附属小学校は日本有数の競技プログラマー養成校として有名です。この学校の教員は幅広い アルゴリズムの知識を持ち、日々それを活用しています。教員であるあなたは、今年は図画工作の授業 を担当することになりました。この授業では、児童全員がそれぞれ1年間で一つの課題を完成させることになっています。授業の概要は以下のとおりです。

  • 1年間で授業は D 回(同じ日に2 回以上授業はない)あり、その全てが課題制作に充てられる。
  • 制作する課題は M 種類用意されている。
  • それぞれの児童に、M 種類の中から課題を1つずつ割り当てる。
  • 児童は N 人であり、N 人それぞれに異なる課題が割り当てられる。

児童は、K 種類ある部品のうちいくつかの種類の部品を使用して課題を完成させます。課題の制作の概要は以下のとおりです。

  • 課題ごとに、使用すべき部品の種類と数はあらかじめ決められている。
  • 課題が完成するまでに使用する部品の種類と数は、その課題で使用すべき部品の種類と数に、過不足なく一致していなければならない。
  • 異なる課題でも、使われる部品の種類と数がすべて同じ場合もある。
  • どの課題も、同じ種類の部品は2個までしか使用できない。
  • 部品を使用する順序は課題の完成に影響を与えない。
  • いくつかの部品が入っている袋が事前に P 個用意されている。ただし、異なる袋でも、入っている部品の種類と数がすべて同じ場合もある。
  • 教員は、児童1人につき袋を1つだけ渡すことができる(袋を渡さない児童がいてもよい)。
  • 2人以上の児童に同じ袋を渡すことはできない(反対に、誰にも渡されない袋があってもよい)。
  • 袋を渡された児童は、袋の中に入っている部品をすべて、自分が制作する課題に使わなければならない。

袋に入っている部品以外で課題に使用する部品は、別途購入する必要があります。部品の購入に関する条件は以下のとおりです。

  • 部品は授業の日だけ購入でき、その日にしか使えない。
  • それぞれの課題について、1回の授業でL個までの部品を購入することができる。
  • 部品の種類によって価格が設定されており、購入する日によって価格が変動する。ただし、どの種類も品切れになることはない。

あなたは、このような条件下で、授業にかかる経費をなるべく抑えたいと考えています。そこで、児童全員の部品購入費の合計の最小値を計算するプログラムを作成することにしました。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ3つの行で示される。各データセットは以下の形式で与えられる。

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

各行で与えられる数値は1つの空白で区切られている。

D(1 ≤ D ≤ 8)は授業の回数、K(1 ≤ K ≤ 8)は部品の種類の数、L(1 ≤ L ≤ 8)は1日に購入することができる部品の数を示す。cd,k (1 ≤ cd,k ≤ 100)は d 日目の部品k の価格を示す。

M(1 ≤ M ≤ 200)は課題の種類の数、N(1 ≤ N ≤ M)は生徒の人数、P(1 ≤ P ≤ 200)は袋の数を示す。

rm,k (0 ≤ rm,k ≤ 2)は課題 m に必要な部品 k の個数、tp,k (0 ≤ tp,k ≤ 2)は袋 p に入っている部品 k の個数を示す。

部品を1つも必要としない課題や、空の袋は与えられないものとする。

データセットの数は20 を超えない。

出力

データセットごとに、生徒全員の部品購入費の合計の最小値を1行に出力する。N種類の作品を完成させることができない場合は -1 を出力する。

入力例

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

出力例

-1
9
6
7

Source: PC Koshien 2012 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2012-11-10
http://www.pref.fukushima.jp/pc-concours/