오직 0과 1만으로 이루어진 m*n 크기의 행렬이 있습니다. 그 중 다음 조건을 만족시키는 행렬을 “바둑판 행렬”이라고 부릅니다.

어떤 크기 m인 배열 A[1…m]와 크기 n인 배열 B[1…n]가 존재하여 행렬의 i 행 j 열의 원소를 a_ij라 할 때, 모든 i, j(1 ≤ i ≤ m, 1 ≤ j ≤ n)에 대해 a_ij = A[i] xor B[j]을 만족한다.

예를 들어, 아래 행렬들은 “바둑판 행렬”입니다.

1 0 0 1

0 1 1 0

1 0 0 1

0 0

0 0

1 0 1 1 0

0 1 0 0 1

0 1 0 0 1

가온이에게는 0과 1만으로 이루어진 행렬이 있습니다.

가온이는 이 행렬의 어느 원소를 골라 바꾸는 시행을 최대 k번 시행할 수 있습니다. 가온이는 이 시행을 최소로 하여 “바둑판 행렬”을 만들고 싶어합니다. 만약 k번 안에 가능하다면 이 시행의 최솟값을, 불가능하다면 “-1”을 출력하세요.

바둑판 만들기 timer 1s memory 128MB

바둑판 만들기 1s 128MB