항승이네 마을에서 결혼이란 일반적인 결혼과는 약간 다르다. 항승이네 마을에서 결혼이란 한 명의 남편과 여러 명의 부인, 또는 여러 명의 남편과 한 명의 부인을 의미한다.</p>

항승이네 마을에 남자가 총 N명, 여자가 총 M명 있다. 어떤 남자와 어떤 여자가 결혼을 하려면, 서로가 서로에게 호감이 있어야 한다.

항승이가 마을의 촌장으로써 할 일은 남자와 여자를 결혼을 시키는 것인데, 가능한 결혼의 개수를 최소화시키는 것이다. 모든 사람은 반드시 하나의 결혼을 해야만 한다. 즉, 결혼을 하지 않는 경우는 없다. 그 때 가능한 결혼의 수의 최솟값을 구하는 프로그램을 작성하시오. 모든 사람이 결혼을 할 수 없는 경우에는 -1을 출력한다.

입력 형식

첫째 줄에 N과 M이 주어진다. N과 M은 12보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에는 i번 남자와 1,2,3,...M번 여자가 호감이 있으면 1 없으면 0이 주어진다.

출력 형식

첫째 줄에 결혼의 개수의 최솟값을 출력한다. 만약 모든 사람이 결혼을 할 수 없으면 -1을 출력한다.

예제 입력 1

4 4
0001
0001
0001
1111

예제 출력 1

2

예제 입력 2

1 3
111

예제 출력 2

1

예제 입력 3

2 2
00
00

예제 출력 3

-1

예제 입력 4

3 3
100
010
001

예제 출력 4

3