题目描述

Smart 想投资赚钱。

根据 Smart 的理论，他的投资行为将会遵循以下的模式：

1. Smart 的交易终端会自动计算出某种权证的最优持有数目。Smart 要么不持有这种权证，要么就会持有这种权证的最优持有数目。
2. 为了节省精力，Smart 在每天只会对同一种权证进行一次买入或卖出操作。

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

在正式开始前，Smart 找来了这 \(m\) 种权证在历史上连续 \(n\) 天内的价格情况进行演练。

现在，Smart 想知道：假设这些价格信息是已知的，他最快能在第几天获得至少 \(b\) 收益？

由于我们显然可以通过用最优持有数目和单位权证价格之积代替原价格来忽略最优持有数目的值对结果的影响，我们可以重新表述原问题如下：
给定 \(m\) 种权证在连续 \(n\) 天内的价格，每种权证在同一天内只能买入或卖出共计至多一次，
每种权证的持有数目只能为 \(0\) 或 \(1\)，初始资金足够多，求获得至少 \(b\) 收益的最短时间。

格式

输入格式

输入的第 \(1\) 行包含 \(3\) 个整数 \(n,m,b\)，意义见题目描述。
接下来 \(m\) 行，每行包含 \(n\) 个整数，第 \(i\) 行第 \(j\) 个数描述第 \(i\) 种权证在第 \(j\) 天的价格。

输出格式

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

样例1

样例输入1

3 2 10
5 2 8
0 3 5

样例输出1

3

样例解释

Smart 只需在第 \(1\) 天买入第 \(2\) 种权证，在第 \(2\) 天买入第 \(1\) 种权证，并在第 \(3\) 天全部卖出就能得到 \(11\) 收益。

限制

对于全部数据，有 \(1<= n <=5000，1<=m<= 200，0<= b <=^109，0 <=\) 权证价格 \(<=10000\)。
下表中留空的位置代表该测试点在这一项目上没有特殊约定。数据范围中给出的 \(n\) 的个位上的值可以帮助你判断测试点的类型。

测试点编号	\(n\)	\(m\)	特殊约定
\(1,2\)	\(≤15\)	\(≤10\)	无
\(3,4,5\)	\(≤1000\)	\(≤50\)	无
\(6\)	\(=4998\)	无	保证全部 \(m\) 中权证各自在 \(n\) 天单调递增
\(7,8\)	\(=4999\)	无	保证存在一组最优解，满足每种权证至多只进行 \(1\) 次买入
\(9,10\)	\(=5000\)	无	无