← 返回题目列表

AtCoder · awc0002_d

D. 钥匙和宝箱

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

分数: 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