题目描述

Dearboy 是一名商品供应商，现在遇到了一个大问题，需要你的帮助。在他的销售区域中有 $N$ 个零售商（编号从 $1$ 到 $N$），这些零售商从他那里进货。Dearboy 有 $M$ 个供应点（编号从 $1$ 到 $M$），每个供应点提供 $K$ 种不同的商品（编号从 $1$ 到 $K$）。当零售商下单时，Dearboy 需要安排从哪些供应点提供多少数量的商品给零售商，以最小化运输总成本。

已知不同种类的商品从不同供应点到不同零售商的单位运输成本可能不同。给定每个供应点的 $K$ 种商品的库存量、$N$ 个零售商对 $K$ 种商品的需求量，以及 $K$ 种商品从不同供应点到不同零售商的单位运输成本矩阵，你需要计算出如何安排商品供应，以使运输总成本最小。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含三个整数 $N$, $M$, $K$（$0 < N, M, K < 50$），含义如上所述。接下来的 $N$ 行给出零售商的需求，每行包含 $K$ 个整数（整数范围在 $[0, 3]$ 内），表示每个零售商对每种商品的需求量。接下来的 $M$ 行给出供应点的库存，每行包含 $K$ 个整数（整数范围也在 $[0, 3]$ 内），表示该供应点每种商品的库存量。

然后是 $K$ 个整数矩阵（每个矩阵的大小为 $N \times M$），第 $k$ 个矩阵的第 $i$ 行第 $j$ 列的整数（整数范围在 $(0, 100)$ 内）表示将第 $k$ 种商品的 $1$ 个单位从第 $j$ 个供应点运输到第 $i$ 个零售商的成本。

输入以三个 "0" 结束，该测试用例无需处理。

输出格式

对于每个测试用例，如果 Dearboy 能够满足所有零售商的所有需求，则在一行中输出一个整数，表示最小运输成本；否则输出 "-1"。

输入样例 1

1 3 3   
1 1 1
0 1 1
1 2 2
1 0 1
1 2 3
1 1 1
2 1 1

1 1 1
3
2
20

0 0 0

输出样例 1

4
-1

来源

POJ Monthly--2005.07.31, Wang Yijie