ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2091. Естественный отбор

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие зимние вечера по-своему. Никите же в этом году не до развлечений. Ещё бы — ведь ему всего через полгода поступать на матмех. Поэтому Никита уже сейчас выбирает для себя специальность, куда пойти учиться. В последнее время их появилось на матмехе столько, что очень трудно сравнить их все между собой и сделать правильный выбор.
Для начала Никита узнал, какие предметы преподают на каждой из специальностей. После этого он хочет выбрать пару предметов A и B и разбить все специальности на четыре множества (некоторые из которых могут быть пустыми):
  1. Специальности, на которых преподают как предмет A, так и предмет B.
  2. Специальности, на которых преподают предмет A, но не преподают предмет B.
  3. Специальности, на которых не преподают предмет A, но преподают предмет B.
  4. Специальности, на которых не преподают ни предмет A, ни предмет B.
Никите хочется, чтобы размер самого большого множества из этих четырёх был как можно меньше. Какие предметы A и B для этого он должен выбрать?

Исходные данные

В первой строке даны целые числа n и m — количество специальностей на матмехе и количество преподаваемых предметов (4 ≤ n, m ≤ 100). В следующих n строках записано по m чисел 0 или 1. j-е число в i-й строке равно единице, если на i-й специальности преподают j-й предмет, и нулю в противном случае.

Результат

В первой строке выведите размер максимального множества из описанных четырёх при оптимальном разбиении. Во второй строке выведите два различных целых числа в пределах от 1 до m — номера предметов, которые должен выбрать Никита. Если задача имеет несколько оптимальных решений, можно вывести любое из них.

Пример

исходные данныерезультат
6 4
0 0 0 1
0 0 1 0
0 1 1 1
1 1 1 1
0 0 0 0
1 0 0 1
2
1 3

Замечания

Выбор предметов 1 и 3 разбивает все специальности на следующие множества: {4}, {6}, {2, 3}, {1, 5}.
Автор задачи: Дмитрий Иванков
Источник задачи: Открытое личное первенство УрФУ по программированию 2014