EduBrick

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

3000 мс · 256 МБ · всё или ничего

Есть nn юношей и mm девушек, для каждой пары известен коэффициент совместимости. Падишах хочет создать максимально возможное число семей, а среди всех таких способов выбрать тот, в котором наименьшая совместимость в семье как можно больше.

Нужно вывести этот наименьший коэффициент.

Формат ввода

В первой строке nn и mm (1≤n,m≤2001 \le n, m \le 200). В следующих nn строках по mm целых чисел от 00 до 10910^9 — коэффициенты совместимости.

Формат вывода

Выведите наименьший коэффициент, при котором возможно создание максимально возможного числа семейных пар.

Примеры

ввод
3 4
77 88 31 67
96 30 2 68
35 39 76 45
вывод
76
ввод
1 1
0
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.