시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB21121168.750%

문제

Given an integer array $x$ consisting of integers (namely, each item of $x$ is an integer), the Closest Position array (CP-array) $\text{CP}(x)$ is an array of length $|x|$ defined to be

$\text{CP}(x)[i] = \max(\{j ∣ j < i; x[j] ≥ x[i]\} ∪ \{−1\})$ for all $0 ≤ i < |x|$,

where $x[i]$ denotes the $i$-th integer in $x$, and the length $|x|$ is the number of integers in $x$. In other words, $\text{CP}(x)[i]$ is the greatest index of $x$ that is smaller than $i$ and whose item at that index is greater than or equal to $x[i]$. For example, when $x = [64, 2, 5, 100, 100]$, its CP-array is $\text{CP}(x) = [−1, 0, 0, −1, 3]$, and $|x| = 5$.

We say that two integer arrays $x$ and $y$ are CP-equivalent if $\text{CP}(x) = \text{CP}(y)$. It is obvious that two CP-equivalent integer arrays $x$ and $y$ have the same length. For example, two arrays $x = [64, 2, 5, 100, 100]$ and $y = [3, 1, 2, 4, 1]$ are CP-equivalent because their CP-arrays are the same as $[−1, 0, 0, −1, 3]$.

For an integer array $x$, an integer $a$ and a non-negative integer $i < |x|$, a substitution operation on $x$ at position $i$ into $a$ returns the array $[x[0], x[1], \cdots , x[i − 1], a, x[i + 1], \cdots , x[|x| − 1]]$. For an integer array $x$ and a nonnegative integer $i < |x|$, a deletion operation on $x$ at position $i$ returns the array $[x[0], x[1], \cdots , x[i − 1], x[i + 1], \cdots , x[|x| − 1]]$. Finally, for an integer array $x$, an integer $a$ and a non-negative integer $i ≤ |x|$, an insertion operation on $x$ at position $i$ returns the array $[x[0], x[1], \cdots , x[i − 1], a, x[i], \cdots , x[|x| − 1]]$. An edit operation on $x$ is one of an insertion, a deletion or a substitution at a single position.

Given two integer arrays $x$ and $y$, compute the minimum number of edit operations on $y$ to obtain an array $y'$ satisfying $\text{CP}(x) = \text{CP}(y')$.

For example, let $x = [64, 2, 5, 100, 100]$ and $y = [−5, −5, −5, −5]$. Consider the array $y' = [−5, −6, −5, −4, −5]$. Then, we have $\text{CP}(y') = [−1, 0, 0, −1, 3]$ and therefore $x$ and $y'$ are CP-equivalent. Then, we can obtain the integer array $y'$ applying two edit operations on $y$ and it is minimum.

입력

Your program is to read from standard input. The input consists of three lines. The first line consists of two integers $n$ and $m$ ($1 ≤ n ≤ 40$; $1 ≤ m ≤ 40$) that indicate the length of $x$ and $y$, respectively. The second line consists of $n$ integers between $−1\,000\,000$ and $1\,000\,000$ (both inclusive), representing the array $x$. The third line consists of $m$ integers between $−1\,000\,000$ and $1\,000\,000$ (both inclusive), representing the array $y$.

출력

Your program is to write to standard output. Print exactly one line containing the minimum number of edit operations on $y$ to obtain an integer array $y'$ satisfying $\text{CP}(x) = \text{CP}(y')$.

예제 입력 1

5 5
64 2 5 100 100
3 1 2 4 1

예제 출력 1

0

예제 입력 2

5 4
64 2 5 100 100
-5 -5 -5 -5

예제 출력 2

2

예제 입력 3

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

예제 출력 3

3

예제 입력 4

6 3
1 3 5 2 5 2
5 5 6

예제 출력 4

3