Problem Description

Xiao I is learning to use Pytorch. It is a very popular Python library for machine learning training.

Xiao I noticed that Pytorch has a mechanism for tensor operations called "broadcast". You can think of a tensor as a high-dimensional array. For a $k$-dimensional tensor $A$, we use a sequence of length $k$, $(a_1,a_2,\cdots,a_k)$, to represent the size of each dimension. That is, $A$ is a tensor of shape $a_1 \times a_2 \times \cdots \times a_k$.

For two tensors $A$ and $B$, suppose their dimensions are $(a_1,a_2,\cdots,a_m)$ and $(b_1,b_2,\cdots,b_n)$ respectively. We say $A$ and $B$ are broadcastable if and only if the following property holds:

• For any 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$.

Now Xiao I has two tensors with dimensions $(p_1,p_2,\cdots,p_m)$ and $(q_1,q_2,\cdots,q_n)$. They are not necessarily broadcastable.

So, Xiao I can use Pytorch built-in functions to perform some operations (possibly none). In each operation, he modifies sequence $p$ or $q$ as follows:

• Choose $p$ or $q$, and insert a $1$ at any position in the chosen sequence.

Xiao I wants to know the minimum number of operations needed to make the two tensors broadcastable.

Input Format

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

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

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

Output Format

Output one integer in a single line, representing the minimum number of inserted $1$'s needed to make the two tensors broadcastable.

4 2
2 1 3 2
4 2

1

Hint

Insert a $1$ before the second position of sequence $q$ (getting 4 1 2), and then the two tensors will become broadcastable.

Translated by ChatGPT 5