Работа на кухне ресторана «Бургер Кинг» — настоящее искусство, особенно когда дело касается сборки легендарного Воппера!
Перед вами находится прямоугольный органайзер с ингредиентами, представляющий собой матрицу размера $$$n \times m$$$. Органайзер заполнен настолько разнообразными компонентами (от хрустящего маринованного огурчика до фирменного соуса), что каждый из них уникален. Каждой ячейке присвоен уровень важности от $$$0$$$ до $$$n \cdot m - 1$$$, причём все уровни встречаются ровно по одному разу. Уровень важности ингредиента, расположенного в $$$i$$$-й строке и $$$j$$$-м столбце, равен $$$a_{i, j}$$$.
Чтобы приготовить бургер, вы должны одним аккуратным движением специальной прямоугольной лопатки зачерпнуть из органайзера некоторую прямоугольную подматрицу. Однако лопатка имеет ограниченный размер, поэтому площадь выбранной подматрицы, то есть количество ячеек в ней, не должна превышать $$$k$$$.
Вкус идеального Воппера определяется тем, насколько последовательно собраны базовые ингредиенты. Формально, вкус бургера равен $$$\operatorname{MEX}$$$ множества уровней важности ингредиентов в зачерпнутой подматрице.
Напомним, что $$$\operatorname{MEX}$$$ (Minimum Excluded) множества чисел — это минимальное неотрицательное целое число, которое не принадлежит этому множеству. Например, $$$\operatorname{MEX}$$$ множества $$$\{0, 1, 3, 4\}$$$ равен $$$2$$$, а $$$\operatorname{MEX}$$$ множества $$$\{1, 2\}$$$ равен $$$0$$$.
Пока менеджер ресторана отвернулся к кассе, у вас есть возможность проявить ловкость рук и не более одного раза поменять местами содержимое любых двух различных ячеек органайзера. Вы также можете вовсе ничего не менять.
Определите, какой максимальный вкус Воппера вы сможете получить, если оптимально выполните не более одного обмена, а затем выберете прямоугольную подматрицу ингредиентов.
В первой строке заданы три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 200\,000$$$, $$$1 \le n \cdot m \le 200\,000$$$, $$$1 \le k \le n \cdot m$$$) — размеры матрицы-органайзера и максимально допустимая площадь подматрицы.
В следующих $$$n$$$ строках заданы по $$$m$$$ целых чисел $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \lt n \cdot m$$$) — матрица ингредиентов. Гарантируется, что каждое число от $$$0$$$ до $$$n \cdot m - 1$$$ встречается в матрице ровно один раз.
Выведите единственное целое число — максимально возможный $$$\operatorname{MEX}$$$ подматрицы площади не более $$$k$$$, который можно получить, сделав не более одного обмена элементов.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Итоговый балл за каждую группу равняется максимальному баллу, полученному за эту группу тестов по всем отправленным посылкам.
| Подзадача | Баллы | Дополнительные ограничения | Необх. подзадачи |
| $$$1$$$ | $$$12$$$ | $$$n, m \le 20$$$ | У |
| $$$2$$$ | $$$15$$$ | $$$n = 1$$$ или $$$m = 1$$$ | — |
| $$$3$$$ | $$$18$$$ | $$$k \le 100$$$ | У, 1 |
| $$$4$$$ | $$$22$$$ | ответ не требует обмена | — |
| $$$5$$$ | $$$33$$$ | — | У, 1–4 |
3 3 40 1 82 7 63 5 4
4
1 5 30 1 4 3 2
3
