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