만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이것도 해결해 보시지

시간 제한5초메모리 제한512 MB

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

어려움10점 중 9점

유형
행렬, 동적 계획법, 구간, 수학
정답자
아직 제출이 없습니다

문제

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 구역을 색칠할 수 있다.

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

입력

첫째 줄에 정수 NN과 LL이 주어진다. (1≤N≤2561 \le N \le 256, 1≤N×L≤10240001 \le N \times L \le 1024000)

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

출력

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

예제3

  1. 예제 1

    입력
    1 7
    1 2 2 7 3 3 9
    
    예상 출력
    6
    
  2. 예제 2

    입력
    2 14
    1 0 1 0 1 0 2 2 1 0 2 2 2 2
    0 1 0 1 0 1 2 2 0 1 2 2 2 2
    
    예상 출력
    24
    
  3. 예제 3

    입력
    3 12
    1 2 3 4 5 6 7 8 9 10 11 12
    1 2 3 4 5 6 7 8 9 10 11 12
    1 2 3 4 5 6 7 8 9 10 11 12
    
    예상 출력
    0