D - 枕決め
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
CODE FESTIVAL 2014
の参加者のうち、n 人の人がホテルに宿泊しようとしています。
ホテルには m 個の部屋があり、部屋 i には高さが a_i の枕が置いてあります。 ホテルの部屋はあまり広くないため、1 つの部屋には高々 1 人しか宿泊することができません。 参加者はそれぞれ枕の高さに対して好みがあり、i 番目の参加者は x_i 以上 y_i 以下の高さの枕を好んでいます。
できるだけ多くの参加者が好みの枕を使うことができるようにホテルの部屋を割り当てたときに、好みの枕を使うことができる人数を求めてください。
入力
入力は以下の形式で与えられる。
n m x_1 y_1 ... x_n y_n a_1 ... a_m
- 1 行目には、宿泊する人数を表す整数 n (1 \leq n \leq 100{,}000) と、ホテルの部屋の数を表す整数 m (1 \leq m \leq 100{,}000) が与えられる。
- 続く n 行には、各参加者の枕の高さに対する好みの範囲が与えられる。
- x_i, y_i (1 \leq x_i \leq y_i \leq 100{,}000) は、i 番目の宿泊者が x_i 以上 y_i 以下の高さの枕を好むことを意味する。
- 続く m 行には、ホテルの各部屋にある枕の高さが与えられる。
- a_i (1 \leq a_i \leq 100{,}000) は、i 番目の部屋にある枕の高さが a_i であることを意味する。
出力
できるだけ多くの参加者が好みの枕を使えるようにホテルの部屋を割り当てたときに、好みの枕を使うことができる人数を 1 行で出力せよ。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
3 3 1 2 2 3 3 4 1 2 3
出力例1
3
入力例2
3 3 1 2 2 3 3 4 2 4 5
出力例2
2
入力例3
3 4 1 4 2 3 5 5 2 4 5 6
出力例3
3