做题 (homework)

【题目描述】

​ 小明要开始刷题了。

​ 小明刷题时会有一个烦躁值。首先，小明开始写新的题需要下定决心，烦躁值增加1；其次小明做第 $i$ 题会有一个固定的烦躁值增量 $b_i$ ；最后，小明发现，由于天气太热，烦躁值会和之前积累的烦躁值、题目的难度相关，在这儿小明假设这个关系是线性的，如果之前积累的烦躁值为 $T$ ,则做第 $i$ 题会增长 $a_i\times T$ 的烦躁值。即如果之前烦躁值为 $T$，则做第 $i$ 题增长的烦躁值为 $a_i\times T+b_i+1$ 。

​ 现在小明需要做 $n$ 道题，小明不一定能做完，当小明的烦躁值高于 $P$ 后，小明就一个字都不想看了，并且会特别暴躁，小明不希望自己陷入这样的状态，所以想知道在自己摆烂前至多做多少题（做完后烦躁值需要 $\le P$）。

【输入格式】

第一行一个整数 $n,P$ 。

接下来 $n$ 行,每行 2 个整数 $a_i,b_i$。

【输出格式】

一个整数，表示最多做的题

【样例 $1$ 输入】

5 10
1 4
2 1
3 1
0 2
1 1

【样例 $1$ 输出】

3

小明先做第2题，再做第5题，最后做第4题，此时是一个最优方案

【样例 $2$】

见下发文件

【数据范围】

对于$20\%$的数据，$1\le n\le 8$。

对于额外$10\%$的数据，$a_i=0,\forall i\in[1,n]\cap Z$

对于额外$30\%$的数据，$a_i\neq 0,\forall i\in[1,n]\cap Z$

对于$100\%$的数据，$1\le n\le 2\times 10^5,0\le a_i,b_i,P\le 10^9$。