测试数据来自 system/1009

作业已超过截止时间，您无法递交本题目。

历史记录

10.14 本题数据已加强
10.19 感谢whx大佬指正(伪)std的错误。用新的(伪)std重新生成了数据
11.04 感谢whx大佬指出$h$范围的错误，更新了题面和数据，得到了真正的std！！！（感谢whx大佬）
11.04 同步题目 洛谷U379082 灰灰的飞机
11.05 使用树状数组std跑的数据有误（std写错啦啊哈哈哈哈）重新生成了数据...

题目描述

题目背景

据说灰灰小时候曾指着天上的飞机，说：“我要把这个飞机打下来！”（Meweing跟我说的）

题目内容

灰灰为了实现小时候的梦想，研发了一款打飞机系统。
我们给天上的$N$架飞机从$1$~$N$编号，第$i$架飞机有一个高度$h_i$和一个打击成本$w_i$
但是这套系统有很大的局限性，他只能攻击$N$架飞机中的一个严格上升序列中的飞机；并且打飞机的打击总成本要在区间$[0, W]$内。
现在告诉你所有数据，灰灰想知道他最多能打多少架飞机。

输入格式

第一行两个整数$N, W$
接下来的$N$行，每行两个整数$h_i, w_i$

输出格式

一个整数，最多能打几架飞机

样例

输入

6 5
1 1
2 1
4 1
1 1
3 1
4 1

输出

4

数据规模

对于$20\%$的数据，$1 \leqslant N, W \leqslant 1000$
对于$60\%$的数据，$1 \leqslant N, W \leqslant 1500$
对于$100\%$的数据，$1 \leqslant N, W \leqslant 3000, h \leqslant 10000$

奖励

AC奖励王老师的贴贴一个！！！