← 返回题目列表

AtCoder · abc185_e

E. 序列匹配

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个整数序列 A 长度 N 和一个整数序列 B 长度 M.
高桥将制作新序列 A' 通过删除一些元素(可能为零或全部) A 并连接其余元素。
同样,他将制作另一个新序列 B' 通过删除一些元素(可能为零或全部) B 并连接其余元素。
在这里,他将删除元素,以便 |A'| = |B'|. (|s| 表示长度 s 序列 s.)
让 x 是从中删除的元素总数 A 和 B,和 y 是整数的个数 i 这样 1 \le i \le |A'| 和 {A'}_i \neq {B'}_i。打印最小可能值 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.
这里只有一个整数 i 这样 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_4, B_6 来自 B,我们有 x = 2, y = 1,和 x + y = 3,这是可能的最小值。


示例输入 3

5 5
1 1 1 1 1
2 2 2 2 2

示例输出 3

5

允许从两者中删除任何内容 A 和 B.