Павел наконец решил пригласить Наташу на ужин. Павел скромный студент, поэтому не хочет идти в дорогущий ресторан. Наташа — девушка с высоким вкусом и предпочитает элитарные заведения.
Город Мюнхетен состоит из n улиц и m проспектов. На пересечении любой улицы и проспекта находится один ресторан. Пронумеруем улицы целыми числами от 1 до n, а проспекты — целыми числами от 1 до m. Стоимость ужина в ресторане на пересечении i-й улицы и j-го проспекта составляет cij.
Павел и Наташа решили выбрать ресторан следующим образом. Сначала Наташа выбирает улицу, на которой хочет ужинать, затем Павел выбирает проспект. Наташа и Павел делают свой выбор оптимально: Наташа желает максимизировать стоимость ужина, а Павел — минимизировать. При выборе улицы Наташа учитывает то, что Павел хочет сэкономить. Определите стоимость ужина влюблённой пары.
Выходные данные
Выведите целое число a — стоимость ужина Павла и Наташи.
Примечание
В первом примере, если Наташа выберет первую или третью улицу, то Павел сможет выбрать проспект со стоимостью ужина 1. Поэтому Наташа выбирает вторую улицу, а Павел любой проспект. Таким образом, стоимость ужина равна 2.
Во втором примере какую бы улицу не выбрала Наташа, Павел сможет выбрать проспект такой, что стоимость ужина будет равна 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
4 1 3 5
2 2 2 2
5 4 5 1
|
2
|
|
2
|
3 3
1 2 3
2 3 1
3 1 2
|
1
|