410439: GYM104021 K Largest Common Submatrix

You are given two $$$n \times m$$$ matrices, and the elements of each matrix are ranged from $$$1$$$ to $$$n \times m$$$ and pairwise distinct. You need to find the common submatrix with the largest size between these two matrices.

Example:

Matrix $$$A$$$: $$$$$$\begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6\\ 8 & 7 & 9\\ \end{array}$$$$$$

Matrix $$$B$$$: $$$$$$\begin{array}{ccc} 5 & 6 & 1\\ 7 & 9 & 3\\ 2 & 4 & 8\\ \end{array}$$$$$$

Largest common submatrix: $$$$$$\begin{array}{cc} 5 & 6\\ 7 & 9\\ \end{array}$$$$$$

The first line of input contains two integers $$$n~(1 \le n \le 1000)$$$ and $$$m~(1 \le m \le 1000)$$$, denoting the number of rows and columns of each matrix.

Each of the next $$$n$$$ lines contain $$$m$$$ integers per line, denoting the first matrix $$$A=(a_{i,j})_{n\times m}$$$. And again, each of the next $$$n$$$ lines contains $$$m$$$ integers per line, denoting the second matrix $$$B=(b_{i,j})_{n\times m}$$$.

It is guaranteed that $$$1 \le a_{i,j}, b_{i,j} \le n \times m$$$, and $$$a_{i_1,j_1} \ne a_{i_2,j_2} \wedge b_{i_1,j_1} \ne b_{i_2,j_2}$$$ always holds for each pair of $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$, where $$$i_1 \ne i_2 \vee j_1 \ne j_2$$$.

Output an integer representing the size of the largest common submatrix.

3 4
5 6 7 8
1 2 3 4
9 10 11 12
5 6 8 7
1 2 4 3
12 11 10 9

4

Largest common submatrix in the sample test: $$$$$$\begin{array}{cc} 5 & 6\\ 1 & 2\\ \end{array}$$$$$$