N x L 행렬에서 3N열 구간을 A, B, C 세 개의 N x N 행렬로 나눠 A*B=C가 성립하는 구간들을 서로 겹치지 않게 골라 칠한 칸 수의 최댓값을 구한다.
N×LN \times LN×L 크기의 정수 행렬 MMM이 있다. MMM에서 연속한 열 3N3N3N개를 고른 뒤 왼쪽부터 NNN열씩 끊으면 N×NN \times NN×N 행렬 세 개가 나온다. 이를 순서대로 AAA, BBB, CCC라고 하자. A×B=CA \times B = CA×B=C가 성립하면 이 N×3NN \times 3NN×3N 구역을 색칠할 수 있다.
색칠하려는 구역에 이미 색칠된 칸이 하나라도 있으면 그 구역은 색칠할 수 없다. 순서를 적당히 정해 색칠할 때, 칠할 수 있는 숫자의 최대 개수를 구하라.
첫째 줄에 정수 NNN과 LLL이 주어진다. (1≤N≤2561 \le N \le 2561≤N≤256, 1≤N×L≤10240001 \le N \times L \le 10240001≤N×L≤1024000)
다음 NNN개의 줄에는 행렬 MMM의 각 행이 주어진다. iii번째 줄의 jjj번째 정수가 Mi,jM_{i,j}Mi,j이다. (0≤Mi,j≤76767670 \le M_{i,j} \le 76767670≤Mi,j≤7676767)
칠할 수 있는 숫자의 최대 개수를 출력한다.