Working in the kitchen of "Burger King" is real art, especially when it comes to making the legendary Whopper!
In front of you there is a rectangular organizer with ingredients, represented as a matrix of size $$$n \times m$$$. The organizer is filled with so many different components (from a crunchy pickled cucumber to the signature sauce) that each of them is unique. Each cell has an importance level from $$$0$$$ to $$$n \cdot m - 1$$$, and every level appears exactly once. The importance level of the ingredient located in row $$$i$$$ and column $$$j$$$ is $$$a_{i, j}$$$.
To make a burger, you must use one careful move with a special rectangular spatula and take some rectangular submatrix from the organizer. However, the spatula has limited size, so the area of the chosen submatrix, that is, the number of cells in it, must not exceed $$$k$$$.
The taste of the perfect Whopper is determined by how consistently the basic ingredients are collected. Formally, the taste of the burger is equal to the $$$\operatorname{MEX}$$$ of the set of importance levels of the ingredients in the chosen submatrix.
Recall that $$$\operatorname{MEX}$$$ (Minimum Excluded) of a set of numbers is the smallest non-negative integer that does not belong to this set. For example, $$$\operatorname{MEX}$$$ of the set $$$\{0, 1, 3, 4\}$$$ is $$$2$$$, and $$$\operatorname{MEX}$$$ of the set $$$\{1, 2\}$$$ is $$$0$$$.
While the restaurant manager turned away to the cash desk, you have a chance to use your sleight of hand and swap the contents of any two different cells of the organizer at most once. You may also choose not to change anything at all.
Determine the maximum possible taste of the Whopper that you can get if you optimally make at most one swap and then choose a rectangular submatrix of ingredients.
In the first line, three integers $$$n$$$, $$$m$$$ and $$$k$$$ are given ($$$1 \le n, m \le 200\,000$$$, $$$1 \le n \cdot m \le 200\,000$$$, $$$1 \le k \le n \cdot m$$$) — the dimensions of the organizer matrix and the maximum allowed area of the submatrix.
In the next $$$n$$$ lines, $$$m$$$ integers $$$a_{i, j}$$$ are given in each line ($$$0 \le a_{i, j} \lt n \cdot m$$$) — the matrix of ingredients. It is guaranteed that each number from $$$0$$$ to $$$n \cdot m - 1$$$ appears in the matrix exactly once.
Print one integer — the maximum possible $$$\operatorname{MEX}$$$ of a submatrix with area at most $$$k$$$ that can be obtained after making at most one swap of elements.
The tests for this problem consist of five groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.
| Subtask | Points | Additional constraints | Required subtasks |
| $$$1$$$ | $$$12$$$ | $$$n, m \le 20$$$ | S |
| $$$2$$$ | $$$15$$$ | $$$n = 1$$$ or $$$m = 1$$$ | — |
| $$$3$$$ | $$$18$$$ | $$$k \le 100$$$ | S, 1 |
| $$$4$$$ | $$$22$$$ | the answer does not require a swap | — |
| $$$5$$$ | $$$33$$$ | — | S, 1–4 |
3 3 40 1 82 7 63 5 4
4
1 5 30 1 4 3 2
3
