You are given two square binary matrices img1 and img2, both of size n $\times$ n.

You may translate one of the images by shifting it horizontally (left or right) and vertically (up or down) by any number of units. Any elements shifted outside the matrix boundaries are erased. After the translation, the overlap is calculated as the count of positions where both matrices contain a $1$.

Return the maximum possible overlap between img1 and img2.

Note: A translation does not include any rotation.

Constraints:

• n $==$ img1.length $==$ img1[i].length

• n $==$ img2.length $==$ img2[i].length

• $1 \leq$ n $\leq 30$

• img1[i][j] is either $0$ or $1$.

• img2[i][j] is either $0$ or $1$.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.