시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB42218714853.818%

문제

영식이는 밑에 슈퍼에 가서 매일매일 시도때도 없이 과자를 사먹는다. 그러다보니 자연스럽게 동전이 많아졌다. 민식이가 놀아주지않아서 자연스럽게 왕따가된 영식이는 동전들을 N×M모양으로 배열하고 뒤집는 놀이를 하려고 한다. N과 M은 모두 홀수이다.

편의상 동전의 앞면을 0, 뒷면을 1이라고 한다.

한번 뒤집기를 할 때, 영식이는 어떤 열과 행 중에 하나를 고를 수 있다. 그리고나서 뒤집는 행동을 할 때는, 고른 열이나 행에 있는 모든 동전을 뒤집어야 한다. 0은 1이 되고 1은 0이 된다는 소리다.

영식이는 동전을 열심히 뒤집어서 각 열과 행에있는 1의 개수를 모두 짝수개로 맞추려고 한다.

영식이가 동전을 뒤집어야하는 횟수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 영식이가 동전을 놓은 세로 크기 N과 가로크기 M이 주어진다. N과 M은 1,000보다 작거나 같은 홀수이다. 둘째 줄부터 총 N개의 줄에 영식이가 각각의 줄에 M개의 동전을 놓은 방법이 주어진다.

출력

첫째 줄에 각각의 열과 행에 동전 뒷면의 개수를 모두 짝수로 만들려고 할 때 해야하는 행동의 최솟값을 출력한다. 만약 각각의 열과 행의 동전 뒷면의 개수를 모두 짝수로 만들 수 없다면 -1을 출력한다.

예제 입력 1

3 3
111
011
001

예제 출력 1

2

예제 입력 2

5 3
111
111
111
111
111

예제 출력 2

3

예제 입력 3

3 5
00000
00000
00000

예제 출력 3

0

예제 입력 4

5 5
10101
01010
10101
01010
10101

예제 출력 4

5

힌트

예제 1의 경우 가운데 행을 뒤집고, 가운데 열을 뒤집으면 된다.

출처