問題文

葵は趣味でお菓子作りをしており，作ったお菓子をよく人に配っている． 葵は，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 個のお菓子のうち，袋に入れることができたお菓子をすべてもらう．

ビ太郎はできるだけ多くのお菓子をもらいたいため，もらえるお菓子の個数がなるべく多くなるように，持ってきたお菓子を袋に入れる． 一方，葵はほかの人にもお菓子を配りたいため，ビ太郎がもらえるお菓子の個数がなるべく少なくなるように，持っていくお菓子を選ぶ． ただし，葵はビ太郎が持っている袋の情報を知っている．

お菓子と袋の情報が与えられたとき，ビ太郎がもらえるお菓子の個数を求めるプログラムを作成せよ．

制約

• 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)．
• 入力される値はすべて整数である．

小課題

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 点) 追加の制約はない．

入力例 1

5 3 1
1 9
1 3
1 6
1 1
1 5
1 10
1 5
1 5

出力例 1

2

葵がお菓子 1，3，5 を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない． このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 2 個のお菓子をもらうことができる．

• お菓子 1 を袋 1 に入れる．
• お菓子 5 を袋 2 に入れる．

葵がビ太郎のもらえるお菓子の個数の最大値を 2 より小さくすることはできないため，2 を出力する．

この入力例は小課題 1,2,4,5 の制約を満たす．

入力例 2

5 3 3
1 9
2 3
2 6
3 1
3 5
1 10
2 7
2 5

出力例 2

1

葵がお菓子 1，4，5 を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない． このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 1 個のお菓子をもらうことができる．

• お菓子 1 を袋 1 に入れる．

葵がビ太郎のもらえるお菓子の個数の最大値を 1 より小さくすることはできないため，1 を出力する．

この入力例は小課題 2,4,5 の制約を満たす．

入力例 3

5 5 5
1 9
2 3
3 6
4 1
5 5
1 10
2 7
3 5
4 8
5 6

出力例 3

4

この入力例は小課題 2,3,4,5 の制約を満たす．

入力例 4

3 3 2
1 5
1 5
1 1
1 2
1 2
2 2

出力例 4

1

この入力例は小課題 2,4,5 の制約を満たす．