分数: 300 点
问题
高桥是竞技编程新手,想学习 M 算法。 最初,他的 理解水平 每个 M 算法是 0.
高桥正在逛一家书店,在那里他发现 N 算法书籍。 的 i第本书(1\leq i\leq N) 售价为 C_i 日元(日本的货币)。如果他购买并阅读这本书,他对这本书的理解程度 j-th 算法将增加 A_{i,j} 对于每个 j (1\leq j\leq M)。 没有其他方法可以提高算法的理解水平。
高桥的目标是提高他对所有事物的理解水平 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
输入
输入由标准输入按以下格式给出:
N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{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