4126: 提升技能所需的最小金额
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
# Skill Up
## 题目描述
小高是一个编程竞赛新手，他想学习 $M$ 种算法。最初，他对每种算法的理解程度都是 $0$。
小高在一家书店里，那里有 $N$ 本关于算法的书。第 $i$ 本书（$1 \leq i \leq N$）的售价是 $C_{i}$ 元。如果他购买并阅读这本书，他对第 $j$ 种算法的理解程度将增加 $A_{i,j}$（对于每个 $j$，$1 \leq j \leq M$）。除此之外，没有其他方法可以提高他对算法的理解程度。
小高的目标是使他对所有 $M$ 种算法的理解程度都达到或超过 $X$。请判断这个目标是否可以实现。如果可以实现，请找出实现这个目标所需的最小金额。
输入
## 输入格式
输入按以下格式从标准输入给出：
$ N$ $M$ $X $
$C_{1}$ ${A}_{1,1}$ ${A}_{1,2}$ $\ldots$ $A_{1,M}$
$C_{2}$ ${A}_{2,1}$ ${A}_{2,2}$ $\ldots$ $A_{2,M} $
$\vdots$
$C_{N}$ $A_{N,1}$ ${A}_{N,2}$ $\ldots$ $A_{N,M}$
输出
## 输出格式
如果目标无法实现，输出 `-1`；否则，输出实现目标所需的最小金额。
样例输入 复制
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9样例输出 复制
120提示
## 输入输出样例
### 输入样例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】
购买第二本和第三本书的话，120元就可以使他对所有算法的理解程度达到或超过 10，这是可能的最小花费。
【样例说明2】
即使购买所有的书，也不足以使他对所有算法的理解程度达到或超过 10。
【 数据范围】
- 所有输入值都是整数,
- $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}$
## 题目来源
ABC167C