작업 배정

N명의 작업자와 M개의 작업이 있다. 각 작업자가 수행할 수 있는 작업이 인접 행렬로 주어진다.

작업자와 작업을 팀으로 묶으려고 한다. 하나의 팀은 다음 중 하나의 형태이다:

• 한 명의 작업자와 여러 개의 작업 (작업자가 모든 작업을 담당)
• 여러 명의 작업자와 한 개의 작업 (작업자들이 하나의 작업을 공동 담당)

팀에 속한 모든 구성원은 서로 연결되어 있어야 한다. 즉, 한 명의 작업자 팀장이면 그 작업자가 담당하는 모든 작업과의 호환성이 있어야 하고, 하나의 작업을 중심으로 하면 그 작업에 참여하는 모든 작업자의 호환성이 있어야 한다.

모든 작업자와 모든 작업이 정확히 하나의 팀에 속하도록 하면서, 팀의 수를 최소화하시오. 배정이 불가능한 경우 -1을 출력한다.

입력

첫째 줄에 N과 M이 주어진다. (1 <= N, M <= 12)
둘째 줄부터 N개의 줄에 걸쳐 길이 M의 문자열이 주어진다. i번째 줄의 j번째 문자가 1이면 작업자 i가 작업 j를 수행할 수 있다.

출력

팀의 수의 최솟값을 출력한다. 불가능하면 -1을 출력한다.

입출력 예시

입력 1

4 4
0001
0001
0001
1111

출력 1

2

입력 2

2 2
00
00

출력 2

-1