AT_joig2026final_k お菓子詰め (Packing Snacks)

葵は趣味でお菓子作りをしており，作ったお菓子をよく人に配っている． 葵は，JOI 記念日にビ太郎にお菓子をあげる約束をした． 当日，葵は $ N $ 個のお菓子を作った． お菓子には種類と大きさが存在し，種類は $ 1 $ 以上 $ T $ 以下の整数で表される． また，これらのお菓子には $ 1 $ から $ N $ までの番号が付けられている． お菓子 $ i $ ( $ 1 \leqq i \leqq N $ ) の種類は $ A_i $ で，大きさは $ C_i $ である． 葵は $ N $ 個のお菓子のうち，ちょうど $ M $ 個のお菓子を選んでビ太郎の家に持っていく． ここで $ M $ は $ 1 $ 以上 $ N $ 以下の整数である． ビ太郎は $ M $ 個の袋を持っており，袋には $ 1 $ から $ M $ までの番号が付けられている． 袋 $ j $ ( $ 1 \leqq j \leqq M $ ) には，種類が $ B_j $ でありかつ大きさが $ D_j $ 以下であるお菓子を最大 $ 1 $ 個入れることができる． ビ太郎は，葵が持ってきた $ M $ 個のお菓子のうち，袋に入れることができたお菓子をすべてもらう． ビ太郎はできるだけ多くのお菓子をもらいたいため，もらえるお菓子の個数がなるべく多くなるように，持ってきたお菓子を袋に入れる． 一方，葵はほかの人にもお菓子を配りたいため，ビ太郎がもらえるお菓子の個数がなるべく少なくなるように，持っていくお菓子を選ぶ． ただし，葵はビ太郎が持っている袋の情報を知っている． お菓子と袋の情報が与えられたとき，ビ太郎がもらえるお菓子の個数を求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ T $ $ A_1 $ $ C_1 $ $ A_2 $ $ C_2 $ $ \vdots $ $ A_N $ $ C_N $ $ B_1 $ $ D_1 $ $ B_2 $ $ D_2 $ $ \vdots $ $ B_M $ $ D_M $

標準出力に，ビ太郎がもらえるお菓子の個数を $ 1 $ 行で出力せよ． ---

### 小課題 1. ( $ 12 $ 点) $ T = 1 $ ． 2. ( $ 17 $ 点) $ N \leqq 10 $ ． 3. ( $ 9 $ 点) $ N = M = T $ ， $ A_i = B_i = i $ ( $ 1 \leqq i \leqq N $ )． 4. ( $ 36 $ 点) $ N \leqq 5\,000 $ ． 5. ( $ 26 $ 点) 追加の制約はない． --- ### Sample Explanation 1 葵がお菓子 $ 1，3，5 $ を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない． このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 $ 2 $ 個のお菓子をもらうことができる． - お菓子 $ 1 $ を袋 $ 1 $ に入れる． - お菓子 $ 5 $ を袋 $ 2 $ に入れる． 葵がビ太郎のもらえるお菓子の個数の最大値を $ 2 $ より小さくすることはできないため， $ 2 $ を出力する． この入力例は小課題 $ 1,2,4,5 $ の制約を満たす． --- ### Sample Explanation 2 葵がお菓子 $ 1，4，5 $ を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない． このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 $ 1 $ 個のお菓子をもらうことができる． - お菓子 $ 1 $ を袋 $ 1 $ に入れる． 葵がビ太郎のもらえるお菓子の個数の最大値を $ 1 $ より小さくすることはできないため， $ 1 $ を出力する． この入力例は小課題 $ 2,4,5 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 2,3,4,5 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 2,4,5 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 500\,000 $ ． - $ 1 \leqq M \leqq \min(N,5\,000) $ ． - $ 1 \leqq T \leqq N $ ． - $ 1 \leqq A_i \leqq T $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq C_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq B_j \leqq T $ ( $ 1 \leqq j \leqq M $ )． - $ 1 \leqq D_j \leqq 10^9 $ ( $ 1 \leqq j \leqq M $ )． - 入力される値はすべて整数である．