← 返回题目列表

AtCoder · hitachi2020_d

D. 漫画市场

中文机器翻译题面 查看原题

分数: 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