시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB4251047233.962%

문제

정수로 이루어진 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보다 작거나 같고, 이차원 배열에 있는 수는 -26보다 크거나 같고, 35보다 작거나 같은 정수이다.

출력

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

예제 입력 1

2 2
-26 2
2 1

예제 출력 1

2

예제 입력 2

1 2
1 2

예제 출력 2

0

예제 입력 3

1 2
10 -2

예제 출력 3

1

예제 입력 4

2 2
-26 9
9 9

예제 출력 4

-1

출처