← 返回题目列表

Codeforces · 387/B

B. 乔治和朗德

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

George 决定准备 Codesecrof 回合,因此他为该回合准备了 m 个问题。让我们用整数 1 到 m 对问题进行编号。 George 通过整数 bi 估计第 i 个问题的复杂性。

为了让这一轮顺利进行,他需要在那里放置至少 n 个问题。此外,他需要至少有一个复杂度恰好为a1的问题,至少一个复杂度恰好为a2的问题,...,以及至少一个复杂度恰好为an的问题。当然,该轮也可能存在其他复杂性的问题。

乔治的想象力很差。对他来说,让一些已经准备好的问题变得更简单比提出一个新问题并准备它更容易。乔治非常擅长简化问题。通过改变输入数据的限制,他可以将任何已经准备好的复杂度为 c 的问题简化为任何正整数复杂度 d (c ≥ d)。

然而,事情并没有这么简单。乔治明白,即使他简化了一些问题,他也可以在一轮中解决所有问题。这就是为什么他决定找出除了他准备的问题之外还需要提出的最少问题数量,以便在一轮比赛中取得好成绩。请注意,乔治可以提出任何复杂的新问题。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 3000) — 一轮好回合中的最少问题数以及 George 准备的问题数。第二行包含空格分隔的整数 a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ 106) — 一轮好的问题复杂性的要求。第三行包含空格分隔的整数 b1, b2, ..., bm (1 ≤ b1 ≤ b2... ≤ bm ≤ 106) — George 准备的问题的复杂性。

输出

打印一个整数——问题的答案。

示例

输入 #1

3 5
1 2 3
1 2 2 3 3

输出 #1

0

输入 #2

3 5
1 2 3
1 1 1 1 1

输出 #2

2

输入 #3

3 1
2 3 4
1

输出 #3

3

注意

在第一个示例中,准备好的问题集满足一轮良好的要求。

在第二个示例中,提出并准备两个复杂度为 2 和 3 的问题就足以获得良好的结果。

在第三个示例中,如果提出并准备复杂的额外问题:2、3、4,则很容易获得良好的结果。