← 返回题目列表

Codeforces · 2164/C

C. 地牢

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

你现在在一个拥有$$$n$$$剑的地牢中,面对$$$m$$$怪物。

第$$$i$$$剑的伤害为$$$a_i$$$,第$$$i$$$怪物的生命值为$$$b_i$$$。当且仅当 $$$x \ge y$$$ 时,一把伤害为 $$$x$$$ 的剑可以杀死生命值为 $$$y$$$ 的怪物。

用伤害$$$x$$$的剑杀死第$$$i$$$个怪物后,这把剑消失。那么,如果$$$c_i \gt 0$$$,你将获得一把伤害为$$$\max(x, c_i)$$$的新剑;否则,你将一无所获。

现在你想知道你可以杀死的怪物的最大数量。请注意,每个怪物最多只能杀死一次。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$T$$$ ($$$1 \le T \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9)$$$。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9)$$$。

每个测试用例的第四行包含 $$$m$$$ 整数 $$$c_1, c_2, \ldots, c_m$$$ ($$$0 \le c_i \le 10^9)$$$。

保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和分别不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——你可以杀死的最大怪物数量。

示例

输入
复制

5
3 2
2 2 2
2 3
3 2
2 3
2 3
2 3 4
0 0 0
3 5
1 7 7
6 6 2 2 2
2 0 0 7 2
4 4
1 5 3 5
7 4 6 5
0 0 1 6
2 2
1 1000000000
1000000000 1
1000000000 0

输出
复制

2
2
5
3
2

注意

展示台链接

在第一个测试用例中,您可以首先使用剑#1杀死怪物#1,并获得伤害$$$\max(2,3)=3$$$的新剑。然后你可以用这把剑杀死怪物#2。

在第二个测试用例中,你无法获得任何新剑,因为所有$$$c_i=0$$$,所以你只能用你现有的两把剑杀死怪物#1和#2。