题目描述

$N$ 個の店があり、それぞれ店 $1$、 店 $2$ 、 $\cdots$ 、店 $N$ という名前が付けられています。高橋君は時刻 $0$ に自宅にいて、これからいくつかの店を訪れる予定です。

高橋君が自宅から各店へ移動する際及び任意の $2$ つの店の間を移動する際に要する時間は $1$ 単位時間です。

高橋君が時刻 $t$ に店 $i$ に着いたとき、その店の列に並び、 $a_i\ \times\ t\ +\ b_i$ 単位時間待つことにより、その店で買い物をすることが出来ます。(待ち時間以外の時間はかからないとします。)

全ての店の閉店時刻は $T\ +\ 0.5$ です。ある店で列に並んでいる途中に閉店時刻を迎えた場合、その店で買い物をすることは出来ません。

高橋君は同じ店で $2$ 回以上買い物をしません。

高橋君が閉店時刻までに買い物を出来る店の数の最大値を答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给定 $n$ 和 $T$，你初始在 $0$ 号点，有 $n$ 个商店，你在任意两个商店或者 $0$ 号点与商店之间往返的时间均为 $1$

当你于时刻 $t$ 到达商店 $i$ 时，你需要花费 $a_i\times t+b_i$ 的时间进行等待（$a_i,b_i$给定），等待完之后，你可以购物，我们假设购物不花费时间也就是说你只有排队等待和往返于商店之间会花费时间。

假定所有商店都会在 $T+0.5$ 时刻关门，你想知道，你最多能在几个不同的商店内购物。

$n\le 2\times 10^5,T,a,b\le 10^9$

translated by Soulist

注意，是到达商店的时间为 $t$ 就会花费 $a\times t+b$ 的时间，所以假设你在 $0$ 时刻走到一个 $a$ 为 $1$ 的商店，那么你的时间结算方式实际上是：

1. 先走过去，时间为 $1$
2. 到达商店，时间花费为 $1\times a+b$，总花费为 $(0+1)\times (a+1)+b$

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$

Sample Explanation 1

店の回り方の例を $1$ つ示します。 - 時刻 $0$ から時刻 $1$ : 自宅から店 $1$ へ $1$ 単位時間掛けて移動します。 - 時刻 $1$ から時刻 $3$ : 店 $1$ で $2$ 単位時間待ち、買い物をします。 - 時刻 $3$ から時刻 $4$ : 店 $1$ から店 $3$ へ $1$ 単位時間掛けて移動します。 - 時刻 $4$ から時刻 $7$ : 店 $3$ で $3$ 単位時間待ち、買い物をします。 以上の回り方では、時刻 $7.5$ までに $2$ 箇所の店で買い物を行うことが出来ます。