问题描述

高桥想学习 $M$ 个不同的算法。

一开始，高桥对所有算法的理解度都是 $0$。

现在有 $N$ 本书，第 $i$ 本书的价格为 $C_i$。如果高桥阅读第 $i$ 本书，那么他对第 $j$ 个算法的理解度会增加 $A_{i,j}$。

高桥可以选择购买并阅读任意本书，每本书最多购买一次。

请你计算：为了让高桥对每一个算法的理解度都至少达到 $X$，最少需要花费多少钱。

如果无论如何都无法让所有算法的理解度达到 $X$，请输出 $-1$。

输入格式

第一行输入三个整数 $N,M,X$，分别表示书的数量、算法的数量以及每个算法需要达到的最低理解度。

接下来 $N$ 行，每行包含 $M+1$ 个整数：

其中 $C_i$ 表示第 $i$ 本书的价格，$A_{i,j}$ 表示阅读第 $i$ 本书后，第 $j$ 个算法的理解度增加值。

输出格式

如果可以让所有算法的理解度都至少达到 $X$，输出所需的最小花费。

如果无法达到要求，输出 $-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

说明

对于样例 $1$，购买第 $1$ 本和第 $3$ 本书需要花费：

此时三个算法的理解度分别为：

仍然有算法没有达到 $10$。

购买第 $1$ 本和第 $2$ 本书需要花费：

三个算法的理解度分别为：

第二个算法仍未达到要求。

最终可以找到花费为 $120$ 的方案，并使所有算法的理解度都至少达到 $10$，因此答案为 $120$。

评测数据规模

对于所有数据：

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