P-Array

There is an N×M array of integers. The array is a P-array if every row sum and every column sum is strictly greater than 0.

In one operation, choose one row or one column and multiply every element in it by -1. Given the array, find the minimum number of operations needed to turn it into a P-array.

The first line contains the number of rows N and the number of columns M. Each of the next N lines contains M integers describing one row of the array.

N and M are at most 18. Every element of the array is an integer from -26 to 35, inclusive.

If the array can be turned into a P-array, print the minimum number of required operations. If it is impossible, print -1.