Solve this one too

Time limit5sMemory limit512 MB

Summary

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.

Level: Hard9 of 10
Topics: Matrix, Dynamic programming, Intervals, Math
Solved: No attempts yet

Problem

You are given an integer matrix $M$ with $N$ rows and $L$ columns. Take $3N$ consecutive columns of $M$ and cut them into three $N \times N$ matrices, $N$ columns at a time from the left. Call them $A$ , $B$ and $C$ in that order. If $A \times B = C$ holds, you may color that $N \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 $N$ and $L$ . ( $1 \le N \le 256$ , $1 \le N \times L \le 1024000$ )

Each of the next $N$ lines contains one row of $M$ . The $j$ -th integer on the $i$ -th of those lines is $M_{i,j}$ . ( $0 \le M_{i,j} \le 7676767$ )

Output

Print the maximum number of numbers that can be colored.

Examples3

Example 1
Input
```
1 7
1 2 2 7 3 3 9
```
Expected output
```
6
```

Example 2

Input

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

Expected output

Example 3

Input

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

Expected output