Description

【题目背景】

时光飞逝，转眼间「第 8 届王权杯权王大赛」已经结束，记者邱神也晋升为主编，两位昔日的「权王大赢家」在如今的主编的邀请下决定再次比拼权证交易技术……

【题目描述】

冠军苏先生在过去的数年间又有了长足的进步，因此这一次比拼他打算基于他总结的一套理论进行权证投资，以此检验理论的正确性。

这场比拼将持续 $n$ 天，在这 $n$ 天中将有 $m$ 种不同的权证供苏先生和邱先生投资。根据苏先生的理论，他的投资行为将会遵循以下的模式：

1.对于每种权证，苏先生可以通过行情分析和历史价格情况在比拼开始前推断出一个最优持有数目。因此，苏先生要么不持有这种权证，要么就会持有这种权证的最优持有数目。

2.为了节省精力，苏先生在每天只会对同一种权证进行一次操作。结合上一条规律，苏先生要么从不持有状态买入为持有状态，要么从持有状态卖出到不持有状态。

在比拼正式开始前，苏先生找来了这 $m$ 种权证在历史上连续 $n$ 天内的价格情况进行演练。

现在他想知道，如果按照他的理论，在已知权证价格的情形下他最快能在第几天获得他想要的收益。

注意：由于苏先生平时的权证投资积累，他拥有大量的初始资金可供调动，因此他不需要关心剩余资金问题（也即不会因为资金不足而无法买入权证）。

由于我们显然可以通过用最优持有数目和单位权证价格之积代替原价格来忽略最优持有数目的值对结果的影响，我们可以重新表述原问题如下：

给定 $m$ 种权证在连续 $n$ 天内的价格，每种权证在同一天内只能买入或卖出共计至多一次，每种权证的持有数目只能为 $0$ 或 $1$，初始资金足够多，求获得至少 $b$ 收益的最短时间。

Input Format

输入的第 1 行包含 3 个整数 $n,m,b$ ，意义见题目描述。

接下来 $m$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 个整数描述第 $i$ 种权证在第 $j$ 天的价格与最优持有数目之积。

Output Format

输出一行一个整数，表示获得 $b$ 收益的最短时间。如果无法获得这么多收益，输出 $-1$。

Sample

【输入输出样例 1】

输入

3 2 10
5 2 8
0 3 5

输出

3

【输入输出样例 2】

输入

3 2 10
5 2 8
0 3 3

输出

-1

Hint

【样例 1 说明】

苏先生只需在第 1 天买入第 2 种权证，在第 2 天买入第 1 种权证，并在第 3 天全部卖出就能得到 $11$ 收益。

对于全部数据，有$1 \le n \le 5000$ ，$1 \le m \le 200$ ，$0 \le b \le 10^9$ ，$0 \le$ 权证价格 $\le 10000$ 。

下表中留空的位置代表该测试点在这一项目上没有特殊约定。数据范围中给出的 $n$ 的个位上的 值可以帮助你判断测试点的类型。