Marriage

In Hangseung's village, marriage works differently from ordinary marriage. One marriage consists of either one husband with several wives, or several husbands with one wife.

There are N men and M women. For a man and a woman to be included in the same marriage, they must like each other.

As the village chief, Hangseung must marry every man and every woman. Each person must belong to exactly one marriage, and nobody may remain unmarried. Find the minimum possible number of marriages. If it is impossible to marry everyone under these rules, print -1.

The first line contains the number of men N and the number of women M. Both N and M are natural numbers not greater than 12.

The next N lines are given. In the i-th of these lines, the j-th character is 1 if man i and woman j like each other, and 0 otherwise.

Print the minimum possible number of marriages. If it is impossible to marry everyone under the rules, print -1.