J1 实践-5 好好学习

佩奇打算学习 $M$ 种算法，最初他对这些算法的理解程度都为 $0$；

佩奇去书店打算买一些书，他发现书店有 $N$ 本书都有涉及这 $M$ 种算法。第 $i$ 本书 ($1\leq i\leq N$)的价格为 $C_i$ 元，如果他将这本书买回去并认真读完，他对第 j 个算法的理解程度将增加 $A_{i,j}$ ($1\leq j\leq M$).

佩奇想使自己对所有算法的理解程度都达到 $x$ 值，他应该怎样购买使得需要支付的钱最少？输出最少需要支付的钱？

输入格式：

如下列格式所示：

N M X
c1 A1,1 A1,2 .....A1,M
c2 A2,1 A2,2 .....A2,M
.
.
.
cN AN,1 AN,2 .....AN,M

输出格式：

输出一个整数，代表最少需要支付的钱，如果不可能，就输出“-1”；

样例输入1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

样例输出1

120

样例输入2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

样例输出2

-1

样例输入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

数据范围：

• $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$