28238번 - 정보 선생님의 야망 스페셜 저지

문제

송도고의 정보 선생님, 박상진 선생님은 송도고를 코딩을 좋아하는 친구라면 누구든지 들어오고 싶어 하는 명성이 자자한 학교로 만들고자 하는 야망이 있다.

박상진 선생님은 이를 위해 주 2ドル$회로 진행되는 알고리즘 특강을 개설하려 한다. 알고리즘 특강을 듣고자 하는 학생은 총 $n$명이며, 각 학생은 월요일부터 금요일까지의 순서대로 각 요일의 수업 참가 가능 여부를 제출하였다. 각 학생은 2ドル$번의 특강에 모두 참가할 수 있어야 특강을 수강할 수 있다.

박상진 선생님을 도와 특강 일정을 어떻게 정해야 최대한 많은 학생이 알고리즘 특강을 수강할 수 있는지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에 알고리즘 특강을 듣고자 하는 학생의 수 $n$이 주어진다.

두 번째 줄부터 $n$개의 줄에 걸쳐 각 $i+1$번째 줄에 $i$번째 학생의 요일별 참가 가능 여부를 의미하는 다섯 개의 정수 $a_{i,1}, \ldots, a_{i,5}$가 공백으로 구분되어 순서대로 주어진다. 각 정수는 0ドル$ 또는 1ドル$이며, 월요일부터 금요일까지의 순서대로 1ドル$이면 학생 $i$가 해당 요일에 참가할 수 있음을, 0ドル$이면 참가할 수 없음을 의미한다.

출력

첫 번째 줄에 특강을 들을 수 있는 학생의 수의 최댓값을 출력한다.

두 번째 줄에 정수 다섯 개를 공백으로 구분하여 출력한다. 각 정수는 0ドル$ 또는 1ドル$이어야 하며, 다섯 개의 정수 중 세 개는 0ドル,ドル 두 개는 1ドル$이어야 한다. 이는 월요일부터 금요일까지의 순서대로 1ドル$이면 특강을 하는 날, 0ドル$이면 특강을 하지 않는 날로 결정했을 때 수강할 수 있는 학생의 수가 최대임을 의미한다. 가능한 특강 일정이 여러 가지인 경우 그중 아무것이나 출력하면 된다.

제한

• 1ドル\le n\le 10^6$.
• 1ドル \leq i \leq n, 1 \leq j \leq 5$에 대해 $a_{i,j}$는 0ドル$ 또는 1ドル$이다.

힌트