C - 合コン大作戦 解説 /

実行時間制限: 3 sec / メモリ制限: 256 MB

問題文

高橋君と青木君は合コンを企画しました。 2 人は N 人の男性と、 M 人の女性を集めることに成功しました。男性には 1 から N の、女性には 1 から M の番号がそれぞれ割り当てられています。企画者である高橋君と青木君の目的はこの合コンで成立するカップルの数を最大化することです。 ここで、カップルとは 1 組の男女のことです。また、それぞれの人は 2 つ以上のカップルに含まれていてはいけません。

i (1≦i≦N) 番の男性は年収が A_i 円であり、年収が B_i 円以上の女性とカップルになりたいと考えています。 j (1≦j≦M) 番の女性は年収が C_j 円であり、年収が D_j 円以上の男性とカップルになりたいと考えています。

高橋君と青木君は i 番の男性と j 番の女性の要求が同時に満たされるとき、すなわち B_i≦C_j かつ D_j≦A_i が満たされるとき、 i 番目の男性と j 番目の女性によるカップルを成立させることが可能です。

この合コンで成立させることができるカップルの数の最大値を調べるのがあなたの仕事です。

入力

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

N M
A_1 B_1
A_2 B_2
:
A_N B_N
C_1 D_1
C_2 D_2
:
C_M D_M
  • 1 行目に男女の数を表す 2 つの整数 N,M (1≦N,M≦150,000) が与えられる。
  • 2 行目からの N 行のうち i (1≦i≦N) 行目には、i 番の男性の年収と相手に要求する年収を表す 2 つの整数 A_i,B_i (1≦A_i,B_i≦10^9) が空白区切りで与えられる。
  • 2+N 行目からの M 行のうち j (1≦j≦M) 行目には、j 番の女性の年収と相手に要求する年収を表す 2 つの整数 C_j,D_j (1≦C_j,D_j≦10^9) が空白区切りで与えられる。

部分点

この問題には部分点が設定されている。

  • 任意の i,j (1≦i≦N,1≦j≦M) において B_i≦C_j を満たすデータセットに正解した場合は 30 点が与えられる。

出力

この合コンで成立させることができるカップルの数の最大値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例 1

3 3
3 5
2 4
4 5
3 1
6 2
5 3

出力例 1

2
  • 1 番の男性と 2 番の女性のカップル、 2 番の男性と 3 番の女性のカップルを成立させたときが、成立するカップルの数が最大になる場合の 1 つであり、成立するカップルの数は 2 です。
  • それぞれの人について、複数のカップルに含まれてはならないことに注意してください。
  • このケースは男性の要求する年収より女性の年収が小さい場合が存在するため、部分点の追加制約を満たしません。

入力例 2

3 4
4 1
2 1
7 1
5 3
12 1
1 10
8 5

出力例 2

3
  • 1 番の男性と 1 番の女性の、 2 番の男性と 2 番の女性の、 3番の男性と 4番の女性のカップルを成立させたときが、成立するカップルの数が最大になる場合であり、その数は 3 です。
  • このケースは部分点の追加制約を満たします。

入力例 3

5 1
1 1
1 1
1 1
1 1
1 1
1 1

出力例 3

1
  • このケースは部分点の追加制約を満たします。

入力例 4

1 1
1 1
1 2

出力例 4

0
  • 成立するカップルの数が 0 の場合もあることに注意してください。
  • このケースは部分点の追加制約を満たします。