이것도 해결해 보시지

N x L 행렬에서 3N열 구간을 A, B, C 세 개의 N x N 행렬로 나눠 A*B=C가 성립하는 구간들을 서로 겹치지 않게 골라 칠한 칸 수의 최댓값을 구한다.

어려움9행렬동적 계획법구간수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

N×LN \times L 크기의 정수 행렬 MM이 있다. MM에서 연속한 열 3N3N개를 고른 뒤 왼쪽부터 NN열씩 끊으면 N×NN \times N 행렬 세 개가 나온다. 이를 순서대로 AA, BB, CC라고 하자. A×B=CA \times B = C가 성립하면 이 N×3NN \times 3N 구역을 색칠할 수 있다.

색칠하려는 구역에 이미 색칠된 칸이 하나라도 있으면 그 구역은 색칠할 수 없다. 순서를 적당히 정해 색칠할 때, 칠할 수 있는 숫자의 최대 개수를 구하라.

입력

첫째 줄에 정수 NNLL이 주어진다. (1N2561 \le N \le 256, 1N×L10240001 \le N \times L \le 1024000)

다음 NN개의 줄에는 행렬 MM의 각 행이 주어진다. ii번째 줄의 jj번째 정수가 Mi,jM_{i,j}이다. (0Mi,j76767670 \le M_{i,j} \le 7676767)

출력

칠할 수 있는 숫자의 최대 개수를 출력한다.