题目描述

随着地摊经济的走红，越来越多的商场步行街都摆出了地摊集市以吸引顾客。小爱来到一个商场也被这商场的地摊集市吸引了，在这集市中有$n$个摊位，第$i$个摊位初始时已有$b_i$位顾客已经在排队，每单位时间会新增$a_i$位顾客。 小爱开始了他的地摊集市之旅，已经从他出发位置到任意摊位、或摊位至摊位之间移动都只需花费$1$单位时间。当小爱在$t$时刻到达$i$摊位时，排在他前面的顾客共$(a_i\times t + b_i)$名，即他需要等待$a_i \times t + b_i$时间，才能买到该摊位的商品。 现在给定$T$表示离集市关门还有$T$时间，问小爱在合理安排购物顺序的情况下，最多能买到多少家不同摊位的商品？

输入格式

第一行，输入两个正整数$n,T$ 接下来$n$行， 每行输入两个正整数$a_i,b_i$

输出格式

输出小爱最多能买到多少家不同摊位的商品

3 8
2 1
2 2
0 3

2

样例解释 1

先到第1个摊位，此时时间为1 在第1个摊位等待时间12+1=3，此时时间为4 去第3个摊位，此时时间为5 在第3个摊位等待时间05+3=3，此时时间为8

数据范围

对于$30$%的数据，$1 \leq n \leq 10$ 对于$50$%的数据，$1 \leq n \leq 10^3$ 对于$70$%的数据，$1 \leq n \leq 10^4$ 对于$100$%的数据，$1 \leq n \leq 10^5$ $0 \leq a_i , b_i \leq 10^9$ $0 \leq T \leq 10^9$