[ARC147E] Examination
题意翻译
有 $n$ 个学生,第 $i$ 个人需要得到至少 $B_i$ 分,但是目前只有 $A_i$ 分。
你可以任意地交换两个学生的分数,以使得所有学生都能得到他需要的分数。
求最多能在多少学生不与别人交换分数的情况下,使得所有学生都能得到他需要的分数。无解输出 $-1$。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc147/tasks/arc147_e
$ 1,2,\ldots,N $ の番号のついた $ N $ 人の生徒が試験を受けました。人 $ i\,(1\ \leq\ i\ \leq\ N) $ の点数は $ A_i $ でしたが、$ B_i $ 点以上取らないと留年です。そこで誰も留年しないように、ある $ 2 $ 人の点数を入れ替える、という操作を任意の回数行うことにしました。
これが可能かを判定し、もし可能ならば一度も点数を入れ替えなかった人数の最大値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ 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
输入样例 #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
说明
### 制約
- $ 2\ \leq\ N\ \leq\ 3\ \times\ 10^5 $
- $ 1\ \leq\ A_i,B_i\ \leq\ 10^9\,(1\ \leq\ i\ \leq\ N) $
- 入力はすべて整数
### Sample Explanation 1
人 $ 1 $ と人 $ 2 $ の点数を入れ替えると、誰も留年しません。このとき、一度も点数を入れ替えなかった人は人 $ 3 $ だけなので、$ 1 $ を出力します。