题目描述

小明打算把 $m$ 种魔法学习到一定等级，他一开始每种算法的魔法都是 $0$ 。现在书店有 $n$ 本魔法书，第 $i$ 本书的价格是 $c_i$ ，如果 $pb$ 选择了买第 $i$ 本书，那么他每种魔法的学习等级会增加 $a_{i,j} (1 \le j \le m)$ 。小明的目标是把 $m$ 种魔法的等级修炼都到 $x$ 或更高，问如果要实现目标，最少需要花费多少钱买书？

输入格式

第一行输入三个整数 $n,m,x$ ，表示书本的数量，魔法的数量，魔法目标等级。

接下来 $n$ 行，第 $i$ 行输入第 $i$ 本书的价格 $c_i$ 和每本书对 $m$ 种魔法能提高的等级数 $a_{i,1},...a_{i,m}$。

输出格式

输出完成目标的最少花费价格，如果目标无法完成，则输出 $-1$ 。

样例 #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

1067

提示

对于$100\%$的数据：

• 所有数字都是整数
• $1 \le n,m \le 12$
• $1 \le x \le 10^5$
• $1 \le c_i \le 10^5$
• $0 \le a_{i,j} \le 10^5$