Зверніть увагу, що у цій задачі вам, можливо, буде корисно використовувати Python 3.10 (PyPy) замість Python 3.13.
Містер IP підготував задачу для майбутнього змагання. Він реалізував рішень і створив тестів.
Однак сьогодні він дізнався, що сервер буде повільнішим, ніж очікувалося, і тепер йому потрібно видалити деякі тести, щоб уникнути довгих черг на оцінювання під час змагання. Він повинен залишити принаймні один і не більше ніж з (t < m) початкових тестів.
Для цього він вирішив придумати якісь критерії для ранжування тестів, щоб зберегти якість тестового набору. Для кожного рішення він виміряв його продуктивність на тестовому наборі і позначив a_{i, j} як витрати часу -го рішення на -му тесті.
Оригінальні тести були створені таким чином, що для будь-яких двох тестів і одне й те саме рішення ніколи не витрачає однакову кількість часу. Іншими словами, для будь-якого 1 \le i \le n і будь-яких 1 \le j, k \le m, якщо j \neq k, то a_{i, j} \neq a_{i, k}.
Природно, містер IP хоче видалити тести, на яких кожне з рішень працює швидко, тому він придумав наступну стратегію — спочатку він визначає додатний цілий параметр , а потім для кожного рішення він позначає як "недійсні" всі тести , для яких існує принаймні інших тестів, на яких це рішення витрачає більше часу, ніж на тесті . Після цього він видаляє всі тести, які позначені як "недійсні" для кожного з рішень. Звичайно, принаймні один тест повинен залишитися після цього.
Оскільки не завжди можливо вибрати таке значення , не видаливши всі тести, ви повинні вивести , коли такого не існує.
Допоможіть містеру IP знайти найбільше значення , для якого він видалить достатньо тестів, щоб в кінці залишилося не більше з них, або встановіть, що такого значення немає.
Перший рядок містить три цілі числа n, m, t (1 \le n \le 1500, 1 \le t < m \le 1500) — кількість рішень, кількість тестів і максимальна кількість тестів, які можуть залишитися після видалення.
Кожен з наступних рядків містить різних цілих чисел: a_{i,1}, a_{i,2}, \ldots, a_{i,m} (1 \le a_{i,j} \le 10^6), де a_{i,j} є часом, витраченим рішенням на тесті . Для кожного фіксованого всі a_{i,j} парно різні.
Виведіть єдине ціле число — максимальне значення , таке що після того, як містер IP видалить всі тести, які позначені як "недійсні" для кожного рішення, кількість залишених тестів буде не більше , або , якщо такого значення не існує.
Приклад 1
Приклад 2
У першому тестовому випадку, з d = 2, для першого рішення тести 2, 3, 5, 6 позначені як "недійсні". Для другого та третього рішень "недійсні" тести це 2, 3, 4, 5 та 3, 4, 5, 6 відповідно.
Ми можемо бачити, що лише тести і є "недійсними" для кожного з рішень, тому лише ці два тести будуть видалені.
Можна перевірити, що для більших значень принаймні тестів залишаються після видалення.
У кожному блоці тести оцінюються незалежно.
( балів): n, m \leq 50;
( балів): n, m \leq 400;
( балів): без додаткових обмежень.