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):
- Programs, which include both course A and course B.
- Programs, which include the course A, but do not include the
course B.
- Programs, which do not include the course A, but include the
course B.
- 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?
Input
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
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.
Sample
input | output |
---|
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
|
Notes
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