У Влада есть \(n\) друзей, для каждого из которых он хочет купить один подарок на Новый год.
Всего в городе есть \(m\) магазинов, в каждом из которых он может купить подарок любому из друзей. Если \(j\)-й друг (\(1 \le j \le n\)) получает подарок, купленный в магазине с номером \(i\) (\(1 \le i \le m\)), то друг получает \(p_{ij}\) единиц радости. Прямоугольная таблица \(p_{ij}\) задана во входных данных.
Влад успевает посетить не более \(n-1\) магазина (\(n\) — количество друзей). Он сам может выбрать, какие именно магазины посетит, и для каких друзей он будет покупать подарки в каждом из них.
Пусть \(j\)-й друг получил \(a_j\) единиц радости от подарка Влада. Найдем величину \(\alpha=\min\{a_1, a_2, \dots, a_n\}\). Цель Влада — купить подарки так, чтобы значение \(\alpha\) было как можно больше. Иными словами, Влад хочет максимизировать минимальную из радостей друзей.
Например, пусть \(m = 2\), \(n = 2\). Пусть радости от подарков, которые мы можем приобрести в первом магазине: \(p_{11} = 1\), \(p_{12}=2\), во втором магазине: \(p_{21} = 3\), \(p_{22}=4\).
Тогда Владу достаточно зайти только во второй магазин и купить в нем для первого друга подарок, приносящий радость \(3\), а для второго — приносящий радость \(4\). При этом величина \(\alpha\) будет равна \(\min\{3, 4\} = 3\).
Помогите Владу выбрать подарки для своих друзей так, чтобы значение \(\alpha\) было максимально возможным. Обратите внимание на то, что каждый друг должен получить один подарок. Влад может посетить не более \(n-1\) магазина (\(n\) — количество друзей). В магазине он может купить произвольное количество подарков.