AT_arc046_c [ARC046C] 合コン大作戦

[problemUrl]: https://atcoder.jp/contests/arc046/tasks/arc046_c 高橋君と青木君は合コンを企画しました。 $ 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) $ が空白区切りで与えられる。

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

### 部分点 この問題には部分点が設定されている。 - 任意の $ i,j\ (1≦i≦N,1≦j≦M) $ において $ B_i≦C_j $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 \- $ 1 $ 番の男性と $ 2 $ 番の女性のカップル、 $ 2 $ 番の男性と $ 3 $ 番の女性のカップルを成立させたときが、成立するカップルの数が最大になる場合の $ 1 $ つであり、成立するカップルの数は $ 2 $ です。 - それぞれの人について、複数のカップルに含まれてはならないことに注意してください。 - このケースは男性の要求する年収より女性の年収が小さい場合が存在するため、部分点の追加制約を満たしません。 ### Sample Explanation 2 \- $ 1 $ 番の男性と $ 1 $ 番の女性の、 $ 2 $ 番の男性と $ 2 $ 番の女性の、 $ 3 $番の男性と $ 4 $番の女性のカップルを成立させたときが、成立するカップルの数が最大になる場合であり、その数は $ 3 $ です。 - このケースは部分点の追加制約を満たします。 ### Sample Explanation 3 \- このケースは部分点の追加制約を満たします。 ### Sample Explanation 4 \- 成立するカップルの数が $ 0 $ の場合もあることに注意してください。 - このケースは部分点の追加制約を満たします。