0060. Проблема падишаха

Имя входного файла:	pairs.in
Имя выходного файла:	pairs.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Мудрый падишах внимательно следит за благополучием своих подданных, когда вершит их судьбы. В частности, на нем все заботы о вступающих в брачный возраст юношах и девушках его страны. И, как положено серьезному правителю, все по науке – перед тем, как творить молодые семьи, падишах провел Глобальное тестирование и по 100-балльной шкале определил совместимость всех юношей и девушек в совместном браке.

А дальше что? Падишах наслышан про задачу о назначении, но ему не нравится ее установка. Действительно, может ли быть спокойна его душа даже в случае всеобщего благополучия, если кому-то из подданных плохо? И можно ли жертвовать интересами хотя бы одной семьи во благо общества? Конечно, нет!

Падишаху милее другая мысль. Он хочет создать семьи таким образом, чтобы степень неблагополучия самой неблагополучной по итогам тестирования пары была наименьшей. А решить эту неклассическую задачу он просит наш клуб программистов. Помогите падишаху!

Формат входного файла

Первая строка данных задачи – два целых числа: 1≤ m≤ 200 – количество девушек и 1≤ n≤ 200 – количество юношей. Последующие m строк содержат по n целых чисел от 0 до 100 – коэффициент совместимости соответствующей пары (меньшее значение менее способствует супружеской жизни).

Формат выходного файла

Ответ – искомый наименьший балл, при котором возможно создание максимально возможного количества семейных пар.

Пример:

pairs.in	pairs.out
3 4 90 30 78 20 70 55 81 72 60 42 87 12	72

Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение



Версия для печати