Gross LCS

The memory limit for this problem is unusually low.

$\operatorname{LCS}(A, B)$ denotes the length of the longest common subsequence of integer sequences $A = \langle a\_1, a\_2, \ldots, a\_n \rangle$ and $B = \langle b\_1, b\_2, \ldots, b\_m \rangle$.

For an integer $x$, $A + x$ is the sequence $\langle a\_1 + x, a\_2 + x, \ldots, a\_n + x \rangle$, obtained by adding $x$ to every element of $A$.

You are given two integer sequences $A$ and $B$. Find the sum of $\operatorname{LCS}(A + x, B)$ over all integers $x$ from $-10^{100}$ to $10^{100}$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 4000$).

The second line contains $n$ integers $a\_1, \ldots, a\_n$ ($-10^8 \le a\_i \le 10^8$).

The third line contains $m$ integers $b\_1, \ldots, b\_m$ ($-10^8 \le b\_i \le 10^8$).

Print the sum of $\operatorname{LCS}(A + x, B)$ over all integers $x$ from $-10^{100}$ to $10^{100}$.

A sequence $P$ is a subsequence of $Q$ if $P$ can be obtained from $Q$ by deleting several elements, possibly zero or all of them. The longest common subsequence of $A$ and $B$ is the longest sequence $C$ that is a subsequence of both.