D - 鍵と宝箱 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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 個でもよい）選び、選んだ宝箱それぞれに鍵を 1 本ずつ割り当てて開けます。ただし、同じ鍵を 2 つ以上の宝箱に割り当てることはできません。また、各宝箱に割り当てた鍵はその宝箱を開けられるもの（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
  • 1 行目には、宝箱の個数を表す整数 N と、鍵の本数を表す整数 M が空白区切りで与えられる。
  • 2 行目には、各宝箱の錠前の強度を表す整数 C_1, C_2, \ldots, C_N が空白区切りで与えられる。
  • 3 行目には、各鍵の開錠能力を表す整数 R_1, R_2, \ldots, R_M が空白区切りで与えられる。

出力

高橋君が開けることのできる宝箱の個数の最大値を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

After a long adventure, Takahashi has reached ruins containing N treasure chests.

Each treasure chest i (1 \leq i \leq N) is secured with a lock of strength C_i. A larger strength value means a sturdier lock. All treasure chests have mutually distinct lock strengths.

Takahashi has M keys. Each key j (1 \leq j \leq M) has an unlocking power R_j. Key j can open treasure chest i only if the key's unlocking power is at least as large as the lock's strength, that is, when C_i \leq R_j. Note that different keys may have the same unlocking power.

Takahashi selects some treasure chests he wants to open (possibly 0), and assigns exactly one key to each selected treasure chest to open it. However, the same key cannot be assigned to two or more treasure chests. Additionally, the key assigned to each treasure chest must be able to open it (C_i \leq R_j). It is fine to leave some keys unused or some treasure chests unopened.

Find the maximum number of treasure chests Takahashi can open.

Constraints

  • 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) (all lock strengths are mutually distinct)
  • All input values are integers

Input

N M
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_M
  • The first line contains an integer N representing the number of treasure chests and an integer M representing the number of keys, separated by a space.
  • The second line contains integers C_1, C_2, \ldots, C_N representing the lock strengths of the treasure chests, separated by spaces.
  • The third line contains integers R_1, R_2, \ldots, R_M representing the unlocking powers of the keys, separated by spaces.

Output

Print the maximum number of treasure chests Takahashi can open, on a single line.

Sample Input 1

3 3
10 20 30
15 25 35

Sample Output 1

3

Sample Input 2

5 3
100 200 300 400 500
150 250 450

Sample Output 2

3

Sample Input 3

7 10
50 120 80 200 350 500 1000
40 60 100 100 150 200 300 400 600 1500

Sample Output 3

7