/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A と、長さ M の整数列 B があります。
高橋君は A から、いくつかの要素を取り除き、残った要素をそのままの順番で繋げることで新たな数列 A' を作ります。(一つも取り除かなくても、全部取り除いても構いません。)
B についても同様に、いくつかの要素を取り除き、残った要素をそのままの順番で繋げることで新たな数列 B' を作ります。(一つも取り除かなくても、全部取り除いても構いません。)
このとき、|A'| = |B'| となるような取り除き方をします。(数列 s について |s| は s の長さを表します。)
A, B から取り除いた合計要素数を x とし、1 \le i \le |A'| かつ {A'}_i \neq {B'}_i を満たす整数 i の数を y とするとき、x + y として考えられる最小の値を求めてください。
制約
- 1 \le N, M \le 1000
- 1 \le A_i, B_i \le 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N
B_1 \hspace{7pt} B_2 \hspace{7pt} B_3 \hspace{5pt} \dots \hspace{5pt} B_M
出力
x + y として考えられる最小の値を出力せよ。
入力例 1
4 3 1 2 1 3 1 3 1
出力例 1
2
A から A_4 を削除して A' を作り、B からは何も削除せず B' を作ることにすると、x = 1 となります。
また、このとき 1 \le i \le |A'| かつ {A'}_i \neq {B'}_i を満たす整数 i は 2 の一つのみなので y = 1 となります。そして x + y は 2 となり、これが最小です。
入力例 2
4 6 1 3 2 4 1 5 2 6 4 3
出力例 2
3
A からは何も取り除かず、B からは B_4, B_6 の 2 要素を削除すると x = 2, y = 1 となり、 x + y は 3 で、これが最小です。
入力例 3
5 5 1 1 1 1 1 2 2 2 2 2
出力例 3
5
A からも B からも何も取り除かないことも許されます。
Score : 500 points
Problem Statement
We have an integer sequence A of length N and an integer sequence B of length M.
Takahashi will make a new sequence A' by removing some elements (possibly zero or all) from A and concatenating the remaining elements.
Similarly, he will make another new sequence B' by removing some elements (possibly zero or all) from B and concatenating the remaining elements.
Here, he will remove elements so that |A'| = |B'|. (|s| denotes the length of s for a sequence s.)
Let x be the total number of elements removed from A and B, and y be the number of integers i such that 1 \le i \le |A'| and {A'}_i \neq {B'}_i. Print the minimium possible value of x + y.
Constraints
- 1 \le N, M \le 1000
- 1 \le A_i, B_i \le 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N
B_1 \hspace{7pt} B_2 \hspace{7pt} B_3 \hspace{5pt} \dots \hspace{5pt} B_M
Output
Print the minimum possible value of x + y.
Sample Input 1
4 3 1 2 1 3 1 3 1
Sample Output 1
2
If we make A' by removing A_4 from A, and B' by removing nothing from B, x will be 1.
Here, there is just one integer i such that 1 \le i \le |A'| and {A'}_i \neq {B'}_i: i = 2, so y will be 1, and x + y will be 2, which is the minimum possible value.
Sample Input 2
4 6 1 3 2 4 1 5 2 6 4 3
Sample Output 2
3
If we remove nothing from A and remove B_4, B_6 from B, we have x = 2, y = 1, and x + y = 3, which is the minimum possible value.
Sample Input 3
5 5 1 1 1 1 1 2 2 2 2 2
Sample Output 3
5
It is allowed to remove nothing from both A and B.