Easily Broadcastable Tensors

Little I is learning to use PyTorch, a very popular Python library for machine learning training.

Little I noticed that PyTorch has a mechanism for tensor operations called 'broadcasting'. You can think of tensors as multidimensional arrays. For a $k$-dimensional tensor $A$, a sequence of length $k$, written $(a_1, a_2, \ldots, a_k)$, gives the lengths of its dimensions. So $A$ is a tensor of size $a_1 \times a_2 \times \ldots \times a_k$.

For two tensors $A$ and $B$, with dimensions $(a_1, a_2, \ldots, a_m)$ and $(b_1, b_2, \ldots, b_n)$, $A$ and $B$ are easily broadcastable if and only if the following holds: for every integer $0 \le i \le \min(n, m) - 1$, either $a_{m-i} = b_{n-i}$, or at least one of $a_{m-i}$ and $b_{n-i}$ is $1$.

Little I has two tensors with dimensions $(p_1, p_2, \ldots, p_m)$ and $(q_1, q_2, \ldots, q_n)$, and they may not be easily broadcastable.

Little I can perform operations (or none) to make them easily broadcastable. Each operation chooses $p$ or $q$ and inserts a $1$ at any position in the chosen sequence.

Find the minimum number of operations required to make the two tensors easily broadcastable.

The first line contains two integers $m$ and $n$ ($1 \le m, n \le 2000$), the dimensions of the two tensors.

The second line contains $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \le p_i \le 2000$), the length of each dimension of the first tensor.

The third line contains $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le 2000$), the length of each dimension of the second tensor.

Print a single integer: the minimum number of insertions of $1$ required to make the two tensors easily broadcastable.

In the sample, inserting a $1$ before the second position of sequence $q$ gives $4, 1, 2$, which makes the two tensors easily broadcastable.