Solve this one too

Given an N x L matrix, find windows of 3N columns split into matrices A, B, C with A*B=C; pick disjoint windows to maximize total colored cells.

Hard9MatrixDynamic programmingIntervalsMathNo attempts yetTime limit5sMemory limit512 MB

Problem

You are given an integer matrix MM with NN rows and LL columns. Take 3N3N consecutive columns of MM and cut them into three N×NN \times N matrices, NN columns at a time from the left. Call them AA, BB and CC in that order. If A×B=CA \times B = C holds, you may color that N×3NN \times 3N region.

If even one cell of the region you want to color is already colored, you cannot color that region. Choose the coloring order so that as many numbers as possible get colored, and find that maximum count.

Input

The first line contains two integers NN and LL. (1N2561 \le N \le 256, 1N×L10240001 \le N \times L \le 1024000)

Each of the next NN lines contains one row of MM. The jj-th integer on the ii-th of those lines is Mi,jM_{i,j}. (0Mi,j76767670 \le M_{i,j} \le 7676767)

Output

Print the maximum number of numbers that can be colored.