Зима в Екатеринбурге — самое длинное время года. И каждый коротает долгие
зимние вечера по-своему. Никите же в этом году не до развлечений. Ещё бы —
ведь ему всего через полгода поступать на матмех. Поэтому Никита уже
сейчас выбирает для себя специальность, куда пойти учиться.
В последнее время их появилось на матмехе столько, что очень трудно
сравнить их все между собой и сделать правильный выбор.
Для начала Никита узнал, какие предметы преподают на каждой из специальностей.
После этого он хочет выбрать пару предметов A и B и разбить все
специальности на четыре множества (некоторые из которых могут быть пустыми):
- Специальности, на которых преподают как предмет A, так и предмет B.
- Специальности, на которых преподают предмет A, но не преподают предмет B.
- Специальности, на которых не преподают предмет A, но преподают предмет B.
- Специальности, на которых не преподают ни предмет 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