分数: 366 分
问题陈述
经过漫长的冒险,高桥到达了废墟,里面有 N 宝箱。
每个宝箱 i (1 \leq i \leq N)用强力锁固定 C_i。强度值越大意味着锁越坚固。所有宝箱都具有互不相同的锁定强度。
高桥有 M 键。每个键 j (1 \leq j \leq M) 具有解锁能力 R_j。钥匙 j 可以打开宝箱 i 仅当钥匙的开锁力至少与锁的强度一样大时,即当 C_i \leq R_j。请注意,不同的钥匙可能具有相同的解锁能力。
高桥选择了一些他想要打开的宝箱(可能是 0),并为每个选定的宝箱分配一把钥匙来打开它。但是,同一把钥匙不能分配给两个或多个宝箱。此外,分配给每个宝箱的钥匙必须能够打开它(C_i \leq R_j)。保留一些未使用的钥匙或一些未打开的宝箱是可以的。
找出高桥可以打开的宝箱的最大数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
- C_i \neq C_k (i \neq k) (所有锁定强度互不相同)
- 所有输入值均为整数
输入
N M C_1 C_2 \ldots C_N R_1 R_2 \ldots R_M
- 第一行包含一个整数 N 代表宝箱数量和一个整数 M 代表键的数量,以空格分隔。
- 第二行包含整数 C_1, C_2, \ldots, C_N 代表宝箱的锁强度,以空格分隔。
- 第三行包含整数 R_1, R_2, \ldots, R_M 代表钥匙的解锁能力,以空格分隔。
输出
在一行中打印高桥可以打开的宝箱的最大数量。
示例输入 1
3 3 10 20 30 15 25 35
示例输出 1
3
示例输入 2
5 3 100 200 300 400 500 150 250 450
示例输出 2
3
示例输入 3
7 10 50 120 80 200 350 500 1000 40 60 100 100 150 200 300 400 600 1500
示例输出 3
7