题目描述

某公司要升级一个产品的 $K$ 种属性，每种初始都是 $0$。有 $N$ 种升级计划，第 $i$ 种花费 $C_i$ 代价给编号为 $j=1, 2, \cdots, K$ 的属性分别增加 $A_{i,j}$，求把所有属性提升到大于等于 $P$ 的最小代价。

输入格式

第一行三个整数 $N$、$K$、$P$。$1 \le N \le 100$，$1 \le K,P \le 5$。

接下来 $N$ 行，每行第一个整数为 $C_i$，接下来 $K$ 个整数为 $A_{i, j}$。$0 \le A_{i,j} \le P$，$1 \le C_i \le 10^9(1 \le i \le N,1 \le j \le K)$。

输出格式

一个整数，表示把所有属性提升到大于等于 $P$ 的最小代价。

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

9

执行第 $1$ 个、第 $3$ 个和第 $4$ 个升级计划后，各属性参数为 $3+2+0=5$，$0+4+1=5$，$2+0+4=6$，全部为 $5$ 以上，因此可以达成目标。在这种情况下，总成本为 $5+3+1=9$。无法找到成本总和不到 $8$ 的升级计划，因此答案是 $9$。

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

-1