Теория игр

Одним из интересных объектов, изучаемых в теории игр, являются так называемые антагонистические игры двух лиц. Такие игры характеризуются множеством X стратегий первого игрока, множеством Y стратегий второго игрока и функцией выигрыша K(x, y) (x из X, y из Y). Если множества стратегий X и Y конечны, то такую игру принято называть матричной, так как функцию выигрыша K в этом случае удобно задавать матрицей.

Рассмотрим матричную игру, в которой X = {1,…,n}, Y = {1,…,m}. Матрицу выигрышей обозначим символом K. Нижним значением игры назовем число max_i=1..nmin_j=1..m K_ij . Верхним значением игры назовем число min_j=1..mmax_i=1..n K_ij. Отметим также, что игры, у которых нижнее и верхнее значение совпадают, называются играми с седловой точкой.

Задана матрица выигрышей K для некоторой матричной игры. Найдите ее верхнее и нижнее значение.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n,m ≤ 100). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно K_ij . Все K_ij по модулю не превосходят 1000.

Выходные данные

В выходной файл OUTPUT.TXT выведите нижнее и верхнее значение игры через пробел.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]