AT_hitachi2020_d Manga Market

有 $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$

请输出答案。

## 限制条件 - 输入均为整数。 - $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 翻译