C 升级

题目描述

小$T$准备开始学$M$个算法。一开始他对$M$个算法的理解程度都是$0$，于是他去了图书馆。图书馆里有$N$本书，第$i\ (1\leq i\leq N)$本售价$C_i$円，如果他买下来（买了就是看了），他对第$j$个算法的理解力将提升$A_{i,j}\ (1\leq j\leq M)$。

现在问你小$T$能不能把对每一个算法的理解力都至少提升到$X$，如果能，算出他达成这个目标最少要花多少钱。

输入格式

第一行三个用空格隔开的整数$N,M,X$。

接下来$N$行，每行$M+1$个用空格隔开的整数$C_i,A_{i,1},A_{i,2},...,A_{i,M}$。

输出格式

如果达不到目标，输出$-1$，否则输出最小需要的花费。

样例数据

input

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

output

120

input

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

output

-1

input

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

output

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$

时间限制：$2 \text {s}$

空间限制：$1024 \text {MB}$