Score : $475$ points

问题描述

AtCoder Inc. 正计划开发一款产品。该产品具有 $K$ 个参数，其当前值全为零。该公司目标是将所有参数值提升到至少 $P$。

共有 $N$ 个开发计划。执行第 $i$ 个开发计划（$1 \le i \le N$）时，对于满足条件 $1 \le j \le K$ 的每个整数 $j$，会使得第 $j$ 个参数的值增加 $A_{i,j}$，同时付出成本 $C_i$。

任一开发计划不可被执行超过一次。判断该公司是否能够实现其目标，如果可以，找出实现目标所需的最小总成本。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

AtCoder Inc. is planning to develop a product. The product has $K$ parameters, whose values are currently all zero. The company aims to raise all parameter values to at least $P$.

There are $N$ development plans. Executing the $i$-th development plan ($1 \le i \le N$) increases the value of the $j$-th parameter by $A_{i,j}$ for every integer $j$ such that $1 \le j \le K$, at the cost of $C_i$.

A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

Constraints

• $1 \le N \le 100$
• $1 \le K,P \le 5$
• $0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)$
• $1 \le C_i \le 10^9(1 \le i \le N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$ $P$

$C_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,K}$

$C_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,K}$

$\dots$

$C_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,K}$

Output

If AtCoder Inc. can achieve its goal, print the minimum total cost required to achieve the goal; otherwise, print -1.

Sample Input 1

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

Sample Output 1

9

If you execute the first, third, and fourth development plans, each parameter will be $3+2+0=5,0+4+1=5,2+0+4=6$, all of which are at least $5$, so the goal is achieved. The total cost in this case is $5 + 3 + 1 = 9$.

It is impossible to achieve the goal at a total cost of $8$ or less. Thus, the answer is $9$.

Sample Input 2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

Sample Output 2

-1

You cannot achieve the goal no matter what you do. Thus, print -1.

update @ 2024/3/10 01:42:53