시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 55 21 16 45.714%

문제

정수로 이루어진 2차원 배열이 P배열이 되려면, 각각의 열에 있는 원소의 합과, 행에 있는 원소의 합이 모두 0보다 커야 한다.

예를 들어,

 2  1 -1
-1  2  2

는 P배열이지만,

 1  1 -1
-1  2  2

는 P배열이 아니다.

세준이는 어떤 행이나 열을 선택한 다음에, 그 행이나 열의 모든 원소의 부호를 바꿀 수 있다. (-1을 곱한다.) 이차원 배열이 주어졌을 때, 이 배열을 P배열로 만들기 위해서 필요한 선택의 회수의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 행의 개수 N과 열의 개수 M이 주어진다. 둘째 줄부터 N개의 줄에 M개이 수가 주어진다. N과 M은 18보다 작거나 같고, 이차원 배열에 있는 수의 절대값은 35보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다. 만약 불가능 할 때에는 -1을 출력한다.

예제 입력

2 2
-26 2
2 1

예제 출력

2

힌트

출처