メルカリ競プロコンテスト2024
コンテスト日時
2024/10/05 (Sa) 13:45 - 15:45

D - レアシューズ

Ceylon
3
s
1024
MB
400

問題文

メルカリには $N$ 個のレアシューズが存在し、$i$ 番目 $(1 \leq i \leq N)$ のレアシューズは、時刻 $x_i$ に出品され、時刻 $y_i$ に出品が終了します。
また、$M$ 人のユーザーがレアシューズを購入しようとしています。$j$ 番目 $(1 \leq j \leq M)$ のユーザーは、時刻 $z_j$ にレアシューズを購入することを希望しており、 $x_i \leq z_j \leq y_i$ を満たすとき、$i$ 番目のレアシューズを購入することができます。ただし、各ユーザーは $1$ つしかレアシューズを購入せず、購入されたレアシューズは他のユーザーが購入することはできなくなります。

各レアシューズをどのユーザーが購入するかを自由に選択できるとき、 最大で何人のユーザーがレアシューズを購入できるかを求めてください。

制約

  • $1 \leq N,M \leq 100{,}000$
  • $0 \leq x_i \leq y_i \leq 10^{9}$
  • $0 \leq z_j \leq 10^{9}$
  • 入力は全て整数

入力

入力は以下の形式で与えられる。

$N$ $M$
$x_1$ $y_1$
$x_2$ $y_2$
$\dots$
$x_N$ $y_N$
$z_1$
$z_2$
$\dots$
$z_M$

出力

答えを整数として出力せよ。

入力例 1
1 1 0 10 5
出力例 1
1
入力例 2
1 1 0 0 100
出力例 2
0
入力例 3
5 5 0 1 1 2 3 4 5 6 2 3 4 1 2 3 5
出力例 3
5
入力例 4
2 2 1 100 2 10 20 5
出力例 4
2
提出
C++23 (g++ 12.2.0)