Marriage

Time limit5sMemory limit128 MB

Summary

Given up to 12 men and 12 women with mutual liking pairs, partition everyone into star-shaped marriages (one person of one gender with several of the other) to cover all people with the fewest marriages, or report impossibility.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Graph, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples4

Example 1
Input
```
4 4
0001
0001
0001
1111
```
Expected output
```
2
```
Example 2
Input
```
1 3
111
```
Expected output
```
1
```
Example 3
Input
```
2 2
00
00
```
Expected output
```
-1
```
Example 4
Input
```
3 3
100
010
001
```
Expected output
```
3
```