Background

After several failures, the little frog's thoughts began to change.

He started to seek his essence as a frog.

He began to seek help from other frogs.

He was undergoing transformation.

He was ascending.

He, would become light!

He gave himself a new name — Frog Cyan (qwq), because the name is cute.

Problem Description

White light can be decomposed into cyan light and many other colors of light.

$\{a\}$ is a sequence of length $n$ with $k$ different colors, where the $i$-th element has color $a_i$ (ensuring that colors $1$ through $k$ all appear in $a$).

$\{b\}$ is a sequence of length $m$, where the $i$-th element has color $b_i$ (ensuring that each $b_i$ is one of the $k$ colors, but not necessarily ensuring that all $k$ colors appear in $b$). We can modify several positions in $b$ to obtain a sequence $b'$ of the same length $m$.

We connect points in $b'$ and $a$ with the same color using a line segment of that color.

For example, with $n=3, m=4, k=3, a=\{1,2,3\}, b'=\{1,3,2,2\}$, the connections between them would look like this:

The requirement is that line segments of different colors do not intersect and all $k$ colors must appear in $b$. What is the minimum number of modifications required?

Formally, let $b'$ be the sequence after your modifications that meets the requirements. You need to minimize:

$$ \sum_{i=1}^{m}[b_i \ne b'_i] $$

For the case of $a=\{1,2,3\}, b'=\{1,3,2,2\}$, the connections (between red $2$ and purple $3$) intersect.

But if we modify $b$ to $\{1,2,3,3\}$, the connections do not intersect and meet the above conditions:

Note:

• The case of $b' = \{1,1,4,5\}$ does not intersect, but $b'$ includes colors outside of $k$ colors (with $4$ and $5$), so this $b'$ is not valid.
• The case of $b' = \{1,1,1,1\}$ does not intersect, but $b'$ does not include all colors from $1$ to $k$ (missing $2$ and $3$), so this $b'$ is also not valid.

If no matter how you modify it, the requirements cannot be met, output -1.

Input Format

The first line contains two integers $n, m$, representing the number of elements in sequences $a$ and $b$ respectively.

The second line contains $n$ integers, where the $i$-th integer represents $a_i$.

The third line contains $m$ integers, where the $i$-th integer represents $b_i$.

Output Format

One line, an integer, representing the minimum number of modifications required to meet the requirements.

If no matter how you modify it, the requirements cannot be met, output -1.

Sample Input and Output

Sample Input #1

3 4
1 2 3
1 3 2 2

Sample Output #1

2

Sample Input #2

5 5
1 2 3 4 4
1 2 3 3 3

Sample Output #2

1

Sample Input #3

5 10
1 2 3 4 5
1 2 2 3 2 2 2 4 5 4

Sample Output #3

3

Sample Input #4

10 2
1 2 1 2 2 2 2 2 2 2
2 2

Sample Output #4

-1

Notes

[Explanation of Sample #1]

Modify $\{1,3,2,2\}$ to $\{1,2,2,3\}$.

It can be proven that this is the minimum number of modifications.

[Explanation of Sample #2]

Modify $\{1,2,3,3,3\}$ to $\{1,2,3,3,4\}$.

It can be proven that this is the minimum number of modifications.

This problem has bundled tests and subtask dependencies.

Time limit: 2s.

• For $100\%$ of the data, it is guaranteed that $1 \le n, m \le 2 \times 10^6$, $1 \le a_i, b_i \le n$. Let $\max\limits_{i=1}^n{a_i} = k$, ensuring that $1$ through $k$ all appear in $a$, and $1 \le k \le n$.

见题面 Input 部分

见题面 Output 部分