产品开发

题目描述

AtCoder 公司正在计划开发一款产品。这款产品有 $K$ 个参数，当前值均为 0。公司希望把所有参数的值都提高到至少 $P$。

现有 $N$ 个开发计划。执行第 $i$ 个开发计划 $(1 \le i \le N)$，会以成本 $C_i$ 使第 $j$ 个参数的值增加 $A_{i,j}$，其中 $j$ 为满足 $1 \le j \le K$ 的任意整数。

每个开发计划最多只能执行一次。判断公司能否达成目标；如果能，求出达成目标所需的最小总成本。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

如果 AtCoder 公司能够达成目标，输出达成目标所需的最小总成本；否则输出 $-1$。

样例

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

9

如果执行第 1、3、4 个开发计划，各参数将变为 $3+2+0=5$、$0+4+1=5$、$2+0+4=6$，均不低于 5，达成目标。此时总成本为 $5+3+1=9$。

总成本为 8 或更少不可能达成目标。因此答案为 $9$。

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

-1

无论怎么做都无法达成目标。因此输出 $-1$。

数据范围

• $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)$
• 输入中的所有值均为整数。