결혼

항승이네 마을의 결혼은 일반적인 결혼과 다르다. 하나의 결혼은 남편 한 명과 아내 여러 명으로 이루어지거나, 남편 여러 명과 아내 한 명으로 이루어진다.

남자는 총 N명, 여자는 총 M명이다. 어떤 남자와 어떤 여자가 같은 결혼에 포함되려면 두 사람이 서로 호감을 가지고 있어야 한다.

촌장인 항승이는 모든 남자와 여자를 빠짐없이 결혼시켜야 한다. 한 사람은 정확히 하나의 결혼에만 포함되며, 결혼하지 않는 사람은 없다. 가능한 결혼의 개수를 최소로 만들 때 그 최솟값을 구하라. 모든 사람을 조건에 맞게 결혼시킬 수 없으면 -1을 출력한다.

첫째 줄에 남자의 수 N과 여자의 수 M이 주어진다. N과 M은 12 이하의 자연수이다.

둘째 줄부터 N개의 줄이 주어진다. i번째 줄의 j번째 문자는 i번 남자와 j번 여자가 서로 호감을 가지고 있으면 1, 그렇지 않으면 0이다.

가능한 결혼 개수의 최솟값을 출력한다. 모든 사람을 조건에 맞게 결혼시킬 수 없으면 -1을 출력한다.