시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 59 14 12 26.087%

문제

요즘 선풍적으로 팔리는 카드 중 하나는 앞면의 소녀시대가 새겨진 카드이다. 지원이와 항승이는 돈을 모아서 이 카드를 R*16개 사서 R*16 행렬로 나란히 정렬하여 놓았다. 그리고 평소 소녀시대에 환장하는 항승이는 모든 카드를 소녀시대가 그려져있는 앞면으로 놔둔채 흐뭇하게 감상하고 있었다.

하지만 소녀시대 중 한 멤버를 지독히 싫어하던  지원이는 그 멤버가 새겨진 카드들을 뒤집어 안 보이게하길 원하고 있다.

지원이는 카드 뒤집기 능력이 뛰어나 한 번에 가로나 세로로 연속된 카드들을 뒤집을 수 있다. 하지만 항승이가 잠시 홀려있는 상태에 있을 때 순식간에 뒤집어야하기 때문에 뒤집는 횟수를 최소한 줄이려 한다. (뒤집는 카드 수가 아닌 뒤집는 연산의 수인 것에 주의한다) 이런 지원이의 고민을 도와주자.

입력

첫 번째 줄에 카드 행의 수인 R (1 ≤ R ≤ 50)이 주어진다. 다음 R개의 줄에 길이가 16인 '0' 또는 '1'로 구성된 문자열이 주어진다. '0'은 지원이가 싫어하지 않는 멤버가 그려져 있는 카드, '1'은 지원이가 싫어하는 멤버가 그려져 있는 카드이다.

출력

뒤집는 연산의 최소 개수를 출력한다.

예제 입력

5
0000111111110000
0010000000000000
1101111111111111
0010000000000000
0000000000000000

예제 출력

3

힌트