题目描述
有 $n$ 个男生，学号为 $1$ 到 $n$，每人有一个 $H$ 值和 $G$ 值。将这 $n$ 个男生分班，要求如下：
1. 分班必须按顺序，不能在一个班上出现学号不连续的情况且每个学生必须要被分到某个班上。
2. 每班的 $H$ 值定义为该班 $H$ 值最高的同学的 $H$ 值。所有班的 $H$ 值之和不得超过 $Limit$。
3. 每个班的 $G$ 值为该班中所有同学的 $G$ 值之和。在满足条件 $1,2,3$ 的情况下，分班应使得 $G$ 值最高的那个班的 $G$ 值最小。
输入
第一行仅 $2$ 个正整数 $n,Limit$，分别为学生数量和 $H$ 值之和的上限。
接下来 $n$ 行每行 $2$ 个正整数 $H_i,G_i$，分别为学号为 $i$ 的学生的 $H$ 值和 $G$ 值。
输出
仅 $n$ 个正整数，表示满足分班的条件下 $n$ 值最高的班级的 $n$ 值。
样例输入输出
输入#1
复制
4 6
4 3
3 5
2 2
2 4
提示
【样例说明】
分班按照 $(1,2)$、$(3,4)$ 进行，这时班级 $H$ 值之和为 $4+2=6\leq Limit$，而 $G$ 值最高的班级为 $(1,2)$，为 $8$。容易看出该分班方案可得到最佳答案。
【数据范围】
对于 $20\%$ 的数据，$n,Limit \leq 100$；
对于 $40\%$ 的数据，$n \leq 1000$；
对于 $100\%$ 的数据，$1 \leq n,G_i \leq 20000$，$1 \leq H_i,Limit \leq 10^7$。