C - 技能提升

分数：300分

问题描述

高桥是一名编程竞赛的新手，他想要学习$M$种算法。

最初，他对每种算法的理解水平都是$0$。 高桥来到了一家书店，这里有$N$本关于算法的书。

第$i$本书（$1\leq i\leq N$）的售价为$C_i$日元（日本货币）。如果他购买并阅读这本书，他对第$j$种算法（$1\leq j\leq M$）的理解水平将增加$A_{i,j}$。

没有其他方法可以提升他对算法的理解水平。 高桥的目标是使他对所有$M$种算法的理解水平都达到$X$或更高。判断这个目标是否可以实现。如果可以实现，求出实现目标所需的最小金额。

约束条件

• 输入中的所有值都是整数。
• $1\leq N, M\leq 12$
• $1\leq X\leq 10^5$
• $1\leq C_i \leq 10^5$
• $0\leq A_{i, j} \leq 10^5$

输入

输入通过标准输入给出，格式如下：

NMXC_1A_{1,1}A_{1,2}\cdotsA_{1,M}C_2A_{2,1}A_{2,2}\cdotsA_{2,M}\vdotsC_NA_{N,1}A_{N,2}\cdotsA_{N,M}

输出

如果目标无法实现，输出$-1$；否则，输出实现目标所需的最小金额。

样例输入1

3 3 10

60 2 2 4

70 8 7 9

50 2 3 9

样例输出1

120

购买第二本和第三本书可以使他对所有算法的理解水平都达到$10$或更高，且花费最小。

样例输入2

3 3 10

100 3 1 4

100 1 5 9

100 2 6 5

样例输出2

-1

即使购买所有书籍，也无法使他对所有算法的理解水平都达到$10$或更高。

样例输入3

8 5 22

100 3 7 5 3 1

164 4 5 2 7 8

334 7 2 7 2 9

234 4 7 2 8 2

541 5 4 3 3 6

235 4 8 6 9 7

394 3 6 1 6 2

872 8 4 3 7 2

样例输出3

1067