← 返回题目列表

Codeforces · 436/D

D. 布丁怪物

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

你玩过布丁怪兽吗?在此任务中,使用了该游戏的简化一维模型。

想象一个无限的方格条纹,其单元格用整数按顺序编号。地带的某些单元格有怪物,地带的其他单元格是空的。所有怪物都是布丁做的,所以如果相邻的单元格中有两个怪物,它们就会互相粘在一起(字面意思)。类似地,如果多个怪物位于连续的单元格中,它们都会粘在一起形成一个怪物块。我们将把粘在一起的怪物称为怪物块。一个独立的怪物,没有粘在其他任何人身上,也被认为是一个方块。

在一次移动中,玩家可以拿起任意一块怪物,并通过手的移动将其向左或向右扔。选定的怪物将继续滑动,直到击中其他怪物(或一群怪物)。

例如,如果条带在单元格 1、4 和 5 中包含三个怪物,则只有四种可能的移动:将单元格 1 中的怪物发送到负无穷大,将单元格 4 和 5 中的怪物块发送到正无穷大,将怪物 1 扔到右侧(它将停止在单元格 3 中),将单元格 4 和 5 中的怪物块扔到左侧(它们将停止在单元格 2 和单元格中)。 3)。

试纸条上的一些单元格标有星号。这些是特殊的细胞。游戏的目标是让尽可能多的特殊细胞上有怪物。

您将获得条带上特殊单元格的编号以及所有怪物的初始位置。在最佳游戏中包含怪物的特殊单元的最大数量是多少?

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2000) — 条带上怪物的数量和特殊单元格的数量。

第二行包含n个不同的整数——有怪物的单元格的数量,然后第三行包含m个不同的整数——特殊单元格的数量。保证所有单元格个数均为不超过2·105的正整数。

输出

打印一个整数 - 在最佳游戏中包含怪物的特殊单元格的最大数量。

示例

输入 #1

3 2
1 3 5
2 4

输出 #1

2

输入 #2

4 2
1 3 4 6
2 5

输出 #2

2

输入 #3

4 2
1 8 4 5
7 2

输出 #3

1