分数: 800 点
问题陈述
有 N 名为 Store 的商店 1,存储 2, \cdots,存储 N。高桥当时在他家 0正计划参观其中一些商店。
Takahashi 从他家到其中一家商店或任意两家商店之间需要一个单位时间。
如果高桥到达商店 i 时间 t,他可以在排队后在那里购物 a_i \times t + b_i 时间单位。 (我们假设除了等待之外不需要任何时间。)
所有商店按时关门 T + 0.5。如果高桥此时正在某家商店排队,他就无法在那里购物。
高桥不会在同一家商店购物多次。
找出他在时间之前最多可以购物的次数 T + 0.5.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9
- 0 \leq b_i \leq 10^9
- 0 \leq T \leq 10^9
输入
输入由标准输入按以下格式给出:
N T a_1 b_1 a_2 b_2 \vdots a_N b_N
输出
打印答案。
示例输入 1
3 7 2 0 3 2 0 3
示例输出 1
2
以下是访问商店的一种可能方式:
- 从时间 0 到时间 1:在 1 时间单位,他从家到商店 1.
- 从时间 1 到时间 3:对于 2 单位时间,他站在 Store 队列中 1 去购物。
- 从时间 3 到时间 4:在 1 时间单位,他从商店出发 1 存储 3.
- 从时间 4 到时间 7:对于 3 单位时间,他站在 Store 队列中 3 去购物。
这样他就可以提前两次购物 7.5.
示例输入 2
1 3 0 3
示例输出 2
0
示例输入 3
5 21600 2 14 3 22 1 3 1 10 1 9
示例输出 3
5
示例输入 4
7 57 0 25 3 10 2 4 5 15 3 22 2 14 1 15
示例输出 4
3