题目描述

为了备考 NHOI ，小明需要学习 $m$ 种算法。一开始小明每种算法的水平都是 $0$ ，完全是零基础。

书店有 $n$ 本书，第 $i$ 本书的价格是 $c[i]$ 。

如果小明买了第 $i$ 本书并阅读该书，那么小明的所有 m 种算法的水平都有所提升，其中第 $j$ 种算法水平会提升 $s[i][j]$ 。

为了确保在 NHOI 比赛能获得一等奖，每一种算法的水平都至少要达到 $X$ 。

小明可以获得一等奖吗？如果可以，输出最少的购书费用；如果不行，输出 $-1$ 。

输入格式

第一行，三个整数：$n, m, X$ ( $1 \le n$ , $m \le 12$ , $1 \le X \le 100000$ )。

接下来有 $n$ 行，每行描述一本书的相关信息,格式如下：

c[1]  s[1][1]  s[1][2]  s[1][3]......s[1][m]
c[2]  s[2][1]  s[2][2]  s[2][3]......s[2][m]
......
c[n]  s[n][1]  s[n][2]  s[n][3]......s[n][m]

其中 $1 \le c[i] \le 100000$ 。

输出格式

一个整数。

样例

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

120

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

-1