Test Removal#482

Test Removal

1 second
256 megabytes
Medium

Pay attention, as in this problem you might need to use Python 3.10 (PyPy) instead of Python 3.13.

Mister IP prepared a problem for an upcoming programming competition. He implemented solutions and created tests.

However, today he learned that the judge server will be slower than expected, and now he needs to remove some tests to avoid long judging queues during the contest. He needs to leave at least one and no more than out of (t < m) initial tests.

To do this, he decided to come up with some criteria for ranking the tests to keep the testset's quality. For each solution, he measured its performance on the testset and denoted by a_{i, j} the time consumption of the -th solution on the -th test.

The original tests were made in such a way that for any two tests and , the same solution never consumes an equal amount of time. In other words, for any 1 \le i \le n and any 1 \le j, k \le m, if j \neq k, then a_{i, j} \neq a_{i, k}.

Naturally, Mister IP wants to remove tests on which each of the solutions works fast, so he came up with the following strategy — first he decides a positive integer parameter , then for each solution he marks as "useless" all tests for which there exist at least other tests on which this solution consumes more time than on test . Afterwards, he removes all tests that are marked as "useless" for each of the solutions. At least one test must remain after this process.

Since it may not always be possible to pick such a value of without removing all tests, you must output when such a doesn't exist.

Help Mister IP find the largest value of for which at most tests remain after the process, or report that there is no such value.

Input

The first line contains three integers n, m, t (1 \le n \le 1500, 1 \le t < m \le 1500) — the number of solutions, the number of tests, and the maximum number of tests that may remain after removal.

Each of the next lines contains distinct integers: a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^6) where a_{i,j} is the time consumed by solution on test . For every fixed , all a_{i,j} are pairwise distinct.

Output

Print a single integer — the maximum value of such that after Mister IP removes all tests that are marked "useless" for every solution, the number of remaining tests is at most , or if such a value doesn't exist.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first testcase, with d = 2, for the first solution tests 2, 3, 5, 6 are marked "useless". For the second and third solutions, the "useless" tests are 2, 3, 4, 5, and 3, 4, 5, 6 respectively.

We can see that only tests and are "useless" for each of the solutions, so only these two tests will be removed.

It can be checked that for larger values of at least tests remain after the removal.

Scoring

In each block, the tests are evaluated independently.

  1. ( points): n, m \leq 50;

  2. ( points): n, m \leq 400;

  3. ( points): no additional restrictions.