AT_abc167_c.[ABC167C] Skill Up

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君刚开始学习竞赛编程，他有 $M$ 个想要学习的算法。最初，每个算法的理解度都是 $0$ 。

有一天，高桥君去书店，发现有 $N$ 本参考书在售。第 $i$ 本参考书（ $1\leq i\leq N$ ）售价为 $C_i$ 日元，购买并阅读后，对于每个 $j$ （ $1\leq j\leq M$ ），第 $j$ 个算法的理解度会提升 $A_{i,j}$ 。除此之外，没有其他方式可以提升理解度。

高桥君的目标是让所有 $M$ 个算法的理解度都达到至少 $X$ 。请判断高桥君是否有可能达成目标，如果可以，请计算达成目标所需的最小金额。

输入格式

输入以如下格式从标准输入读入。

$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
```
输入#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

说明/提示

限制条件

所有输入均为整数。
$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$

样例解释 1

如果购买第 $2$ 和第 $3$ 本参考书，则只需花费 $120$ 日元就能让所有算法的理解度都达到 $10$ 以上，这也是所需的最小金额。

样例解释 2

即使购买所有参考书，第 $1$ 个算法的理解度也无法达到 $10$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页