ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural FU Open Personal Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Natural Selection

Time limit: 1.0 second
Memory limit: 64 MB
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. According to Nikita, he has no time for entertainment this year. Sure, because six months later he will try to enter the Institute of Mathematics and Computer Sciences. So now, Nikita should choose a degree program, that he wants to study. Recently, so much new programs appeared at the Institute that it is very difficult to compare them all together and to make the right choice.
At the beginning, Nikita found out what courses are included in each of the programs. After that, he wants to choose two courses A and B and divide all programs into four sets (some of them may be empty):
  1. Programs, which include both course A and course B.
  2. Programs, which include the course A, but do not include the course B.
  3. Programs, which do not include the course A, but include the course B.
  4. Programs, which include neither course A nor course B.
Nikita wants to minimize the size of the largest of these four sets. What courses A and B should he choose for this?


The first line contains integers n and m that are the number of degree programs at the Institute and the number of courses (4 ≤ n, m ≤ 100). The following n lines contain m numbers 0 or 1. The j-th number in the i-th row is equal to 1, if the i-th program includes the j-th course, and 0 otherwise.


Output in the first line the maximum size of four described sets under optimal division. In the second line output two different integers in the range from 1 to m meaning the courses that Nikita should choose. If there are many optimal solutions, you may output any one of them.


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
1 3


The choice of courses 1 and 3 divides all degree programs to the following sets: {4}, {6}, {2, 3}, {1, 5}.
Problem Author: Dmitry Ivankov
Problem Source: Open Ural FU Personal Contest 2014
To submit the solution for this problem go to the Problem set: 2091. Natural Selection