← 返回题目列表

AtCoder · abc167_c

C. 技能提升

中文机器翻译题面 查看原题

分数: 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