/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
1,2,\ldots,N の番号のついた N 人の生徒が試験を受けました。人 i\,(1 \leq i \leq N) の点数は A_i でしたが、B_i 点以上取らないと留年です。そこで誰も留年しないように、ある 2 人の点数を入れ替える、という操作を任意の回数行うことにしました。
これが可能かを判定し、もし可能ならば一度も点数を入れ替えなかった人数の最大値を求めてください。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i,B_i \leq 10^9\,(1 \leq i \leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
誰も留年しないように操作を行うことが可能な場合、一度も点数を入れ替えなかった人数の最大値を出力せよ。
不可能な場合は -1 を出力せよ。
入力例 1
3 1 2 3 1 3 3
出力例 1
1
人 1 と人 2 の点数を入れ替えると、誰も留年しません。このとき、一度も点数を入れ替えなかった人は人 3 だけなので、1 を出力します。
入力例 2
2 100 1 100 1
出力例 2
2
入力例 3
6 3 2 1 6 4 5 1 3 5 5 9 8
出力例 3
-1
入力例 4
6 3 1 4 5 5 2 2 3 5 4 5 1
出力例 4
3
Score : 800 points
Problem Statement
N students, numbered 1,2,\ldots,N, took an examination. Student i\,(1 \leq i \leq N) had to score at least B_i points to graduate, where they actually scored A_i points.
You can repeat the following operation any number of times (possibly zero):
- Choose two students, and swap their scores.
Your goal is to make everyone graduate. Determine whether it is possible. If it is possible, find the maximum number of students whose scores do not change during the process.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i,B_i \leq 10^9\,(1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
If it is possible to make everyone graduate, print the maximum number of students whose scores do not change during the process.
Otherwise, print -1.
Sample Input 1
3 1 2 3 1 3 3
Sample Output 1
1
If you swap scores of Student 1 and 2, everyone can graduate. Here, the number of students whose scores do not change is 1 (only Student 3).
Sample Input 2
2 100 1 100 1
Sample Output 2
2
Sample Input 3
6 3 2 1 6 4 5 1 3 5 5 9 8
Sample Output 3
-1
Sample Input 4
6 3 1 4 5 5 2 2 3 5 4 5 1
Sample Output 4
3