시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 114 38 15 18.519%

문제

명우76는 UCPC 문제를 푸는 것을 매우 좋아했었다. 이젠 아니야(Not anymore).

“이 시간부로 나는 이제 출제자다.”

명우76는 당신의 연습을 위해 다음과 같은 문제를 준비했다.

N×L 크기의 행렬 A가 주어지면, 행렬 내의 연속된 3N 길이의 부분 열을 잡는다. 이때, 이 3N 길이의 부분 열을 N열씩 나눠 3개의 N×N행렬을 만들고 이를 앞에서부터 A, B, C라고 하자. 이때 A×B=C를 만족하면, 행렬 A내에서 선택한 N×3N행렬 부분을 색칠할 수 있다.

하지만 색칠하려고 하는 N×3N 부분 중 일부가 이미 색칠되어 있다면, 당신은 이 부분을 색칠할 수 없다. 이와 같은 규칙이 존재할 때 적당한 순서로 행렬을 색칠해서, 최대한 많은 숫자를 칠하고 싶다. 이때 칠할 수 있는 숫자의 최대 개수를 구하라.

입력

첫 번째 줄에 두 개의 정수 N(1 ≤ N ≤ 256)과 L(1 ≤ N×L ≤ 1,024,000)이 주어진다. 그 후, N개의 줄에 걸쳐 줄마다 행렬 A의 수를 나타내는 정수 Aij (0 ≤ Aij ≤ 7,676,767)가 L개씩 순서대로 주어진다.

출력

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

예제 입력

1 7
1 2 2 7 3 3 9

예제 출력

6

예제 입력 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

예제 출력 2

24

예제 입력 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

예제 출력 3

0

힌트