P배열
시간 제한1초메모리 제한512 MB
N행 M열 정수 배열에서 행이나 열을 뒤집는 연산을 최소 몇 번 사용해야 모든 행과 열의 합이 양수가 되는지, 불가능하면 -1을 구하는 문제입니다.
문제
정수로 이루어진 N×M 배열이 있다. 이 배열이 P배열이 되려면 모든 행의 원소 합과 모든 열의 원소 합이 각각 0보다 커야 한다.
한 번의 선택으로 행 하나 또는 열 하나를 골라 그 안의 모든 원소에 -1을 곱할 수 있다. 주어진 배열을 P배열로 만들기 위해 필요한 선택 횟수의 최솟값을 구하라.
입력
첫째 줄에 행의 개수 N과 열의 개수 M이 주어진다. 다음 N개의 줄에는 각 행의 M개 정수가 주어진다.
N과 M은 18 이하이다. 배열의 각 원소는 -26 이상 35 이하인 정수이다.
출력
배열을 P배열로 만들 수 있다면 필요한 선택 횟수의 최솟값을 출력한다. 불가능하면 -1을 출력한다.