No testdata at current.

题目描述

有 $N$ 家商店，分别被命名为商店 $1$、商店 $2$、$\cdots$、商店 $N$。高桥君在时刻 $0$ 在家，接下来计划访问若干家商店。

高桥君从家前往任意一家商店，或在任意两家商店之间移动时，都需要 $1$ 单位时间。

当高桥君在时刻 $t$ 到达商店 $i$ 时，他需要在该商店排队，等待 $a_i \times t + b_i$ 单位时间后，才能在该商店购物（除了等待时间外不需要其他时间）。

所有商店的关门时间均为 $T + 0.5$。如果在排队等待过程中到达了关门时间，则无法在该商店购物。

高桥君在同一家商店最多购物一次。

请你求出高桥君在关门时间前最多能在多少家商店购物。

输入格式

输入以如下格式从标准输入读入。

$N$ $T$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_N$ $b_N$

输出格式

请输出答案。

3 7
2 0
3 2
0 3

2

1 3
0 3

0

5 21600
2 14
3 22
1 3
1 10
1 9

5

7 57
0 25
3 10
2 4
5 15
3 22
2 14
1 15

3

说明/提示

限制条件

• 输入均为整数。
• $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$

样例解释 1

下面给出一种商店的访问顺序示例：

• 时刻 $0$ 到时刻 $1$：从家到商店 $1$，花费 $1$ 单位时间移动。
• 时刻 $1$ 到时刻 $3$：在商店 $1$ 等待 $2$ 单位时间，完成购物。
• 时刻 $3$ 到时刻 $4$：从商店 $1$ 到商店 $3$，花费 $1$ 单位时间移动。
• 时刻 $4$ 到时刻 $7$：在商店 $3$ 等待 $3$ 单位时间，完成购物。

按照上述路线，高桥君可以在时刻 $7.5$ 前在 $2$ 家商店完成购物。

由 ChatGPT 4.1 翻译