Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача B. Меньшее из зол

Задачу добавил: alef

Успешно сдано решений: 703

Ограничение по времени на тест:2 секунды
Ограничение по памяти на тест:256 мегабайт

Капитон, впрочем, уже и решение проблемы предложил. Надо построить водный стадион, да такой, чтобы лучше, чем соседних царствах и королевствах. Тогда соревнования можно будет на своём поле проводить, и всё для команды будет привычное, и она всенепременно покажет блестящий результат.

Водный стадион — оно, конечно, дело хорошее. Капитон, к тому же, так складно рассуждает, что рядом бы надо несколько гостиниц построить — на соревнования много зрителей приедет. А кроме соревнований захотят на царство посмотреть — тут экскурсионные маршруты организовать можно. Дороги, конечно, придётся отремонтировать — но это уже давно пора сделать. Так что для экономики одни плюсы: и развитие туризма, и улучшение транспортной сети, и рабочие места. Министр экономики Калистрат министра спорта поддержал: надо новые, современные отрасли развивать.

Вот только свободная местность в Пантелеймоновом царстве преимущественно болотистая. А на такие грандиозные планы нужна большая площадка, да и не на окраине — иначе куда экскурсии возить? Калистрат сходу несколько вариантов назвал. Вот, к примеру, часовой завод. Разве сейчас кто часами пользуется? Тех часов, что у короля Генриха производят, на всех желающих хватит. Или порт речной — грузы нынче на автомобилях перевозят. А сад ботанический — от него и вовсе прибыли никакой, одни расходы. Так что место найти несложно.

Пантелеймон догадывается, что ни один из вариантов не будет принят всеми без возражений. Поэтому он велел каждому из m своих министров составить личный рейтинг n объектов, на месте которых можно построить водный стадион. Число n следует приписать тому объекту, который, с точки зрения министра, является наиболее ценным, число n - 1 — тому, который наиболее ценный из остальных, и так далее; рейтинг 1 следует приписать объекту, который наименее ценен по мнению министра.

Пантелеймон хочет предложить министрам для голосования два объекта, на месте которых можно построить водный стадион. Каждый из министров сможет отдать голос за строительство стадиона на месте одного из этих объектов и сделает это согласно своему рейтингу, отдав голос за тот объект, рейтинг которого у этого министра ниже.

Пантелеймон хочет, чтобы победа одного из вариантов выглядела как можно более убедительно, и чтобы разница в количестве голосов была как можно больше. Если существует несколько подходящих пар объектов, Пантелеймон предпочтёт ту пару, у которой наибольшая по абсолютной величине разница суммарных рейтингов.

Ваша задача — определить, какие два объекта Пантелеймону следует предложить для голосования.

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

В первой строке содержатся два целых числа m и n (2 ≤ m ≤ 100,  2 ≤ n ≤ 100) — количество министров и количество объектов, на месте которых можно построить водный стадион.

В каждой из следующих m строк содержатся рейтинги объектов с точки зрения очередного министра. Рейтинг — это число от 1 до n. Рейтинги всех объектов с точки зрения очередного министра различны.

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

В первой строке содержатся два целых числа — номера объектов, которые Пантелеймону следует выставить на голосование. Первым укажите номер того объекта, на месте которого министры согласятся построить водный стадион.

Если существует несколько вариантов ответа, выведите любой.

Система оценки

Подзадача 1 (до 30 очков)

m, n ≤ 10.

Баллы начисляются за каждый пройденный тест.

Подзадача 2 (до 70 очков)

m, n ≤ 100.

Баллы начисляются за каждый пройденный тест.

По запросу сообщается результат проверки на каждом тесте.

Пример

Входные данные
4 6
4 2 6 1 3 5
6 3 1 4 5 2
3 5 2 6 1 4
2 4 5 6 3 1
Выходные данные
6 4
Примечание

Пояснение к ответу: при противопоставлении объектов #4 и #6 все министры, кроме первого, проголосуют за то, чтобы строить водный стадион на месте объекта #6. Суммарный рейтинг объекта #4 составляет 1 + 4 + 6 + 6 = 17, а суммарный рейтинг объекта #6 составляет 5 + 2 + 4 + 1 = 12. Можно убедиться, что разница в 5 — максимально возможная разница в рейтингах при данном раскладе.

Сдать задачу

Задать вопрос жюри по этой задаче