您正在玩一个类似于无限数线上推箱子的游戏。游戏是离散的,因此您只考虑线上的整数位置。
您的起始位置为 $$$0$$$。有 $$$n$$$ 个盒子,第 $$$i$$$ 个盒子位于 $$$a_i$$$ 位置。盒子的所有位置都是不同的。还有$$$m$$$特殊位置,第$$$j$$$个位置是$$$b_j$$$。所有的特殊位置也很明显。
一步操作中,您可以向左或向右移动一个位置。如果您移动的方向有一个盒子,那么您将盒子推到该方向的下一个位置。如果下一个位置被另一个盒子占据,那么该盒子也会被推到下一个位置,依此类推。你不能穿过盒子。你不能把盒子拉向你。
您可以执行任意数量的移动(可能为零)。您的目标是将尽可能多的盒子放置在特殊位置。请注意,某些盒子最初可以放置在特殊位置。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
然后是 $$$t$$$ 测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 分别是盒子的数量和特殊位置的数量。
每个测试用例的第二行包含 $$$n$$$ 不同的整数,按升序 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_1 < a_2 < \dots < a_n \le 10^9$$$; $$$a_i \neq 0$$$) — 框的初始位置。
每个测试用例的第三行包含 $$$m$$$ 按升序排列的不同整数 $$$b_1, b_2, \dots, b_m$$$ ($$$-10^9 \le b_1 < b_2 < \dots < b_m \le 10^9$$$; $$$b_i \neq 0$$$) - 特殊位置。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数——可以放置在特殊位置的盒子的最大数量。
示例
输入 #1
5 5 6 -1 1 5 11 15 -4 -3 -2 6 7 15 2 2 -1 1 -1000000000 1000000000 2 2 -1000000000 1000000000 -1 1 3 5 -1 1 2 -2 -1 1 2 5 2 1 1 2 10
输出 #1
4 2 0 3 1
注意
在第一个测试用例中,您可以向右$$$5$$$:位置$$$1$$$ 上的框被推到位置$$$6$$$ 上,位置$$$5$$$ 上的框被推到位置$$$7$$$ 上。然后你可以向左走$$$6$$$,最终到达位置$$$-1$$$,并将一个盒子推到$$$-2$$$。最后,这些框分别位于位置 $$$[-2, 6, 7, 11, 15]$$$ 上。其中位置$$$[-2, 6, 7, 15]$$$比较特殊,因此答案是$$$4$$$。
在第二个测试用例中,您可以将 $$$-1$$$ 的框推到 $$$-10^9$$$,然后将 $$$1$$$ 的框推到 $$$10^9$$$,并获得答案 $$$2$$$。
第三个测试用例展示了您不允许拉箱子,因此您不能将它们靠近特殊位置。
在第四个测试用例中,所有框都已经处于特殊位置,因此您可以什么都不做,仍然可以获得答案 $$$3$$$。
在第五个测试用例中,特殊位置比盒子少。您可以将 $$$8$$$ 或 $$$9$$$ 向右移动,以便在位置 $$$10$$$ 上放置一些方框。