该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

暑假期间，有些同学会留校住宿。为了便于管理，学校会统计每个宿舍楼中留在学校的学生数量，以及这座宿舍楼的最大容量，然后考虑将所有宿舍楼的学生集中起来重新分配宿舍。

已知：共有 $n$ 座宿舍楼，第 $i$ 座宿舍楼有 $a_i$ 名同学留校，且该楼最多容纳 $b_i$ 名学生。请你计算：若将所有留校同学重新分配，使得占用的宿舍楼数量最少，那么至少需要几座宿舍楼才能容下所有同学？

输入格式

第一行：一个整数 $n$，表示宿舍楼的数量。

此后 $n$ 行：每行输入两个整数 $a_i,b_i$，分别表示第 $i$ 座宿舍楼的留校学生人数和最大容纳人数。

输出格式

一个整数，表示所需宿舍楼的最少数量。

样例

3
50 100
45 60
80 90

2

4
70 80
20 90
100 100
40 60

3

样例 $1$ 解释

共有 $50+45+80=175$ 名学生留校，第 $1,3$ 座宿舍楼可以容纳 $100+90=190$ 名学生，因此至少 $2$ 座宿舍楼就可以容纳得下。

数据规模与约束

对于 $30\%$ 的数据，$1≤n≤3，1≤a_i≤b_i≤100$。

对于 $60\%$ 的数据，$1≤n≤10，1≤a_i≤b_i≤1000$。

对于 $100\%$ 的数据，$1≤n≤10^6，1≤a_i≤b_i≤10^9$。