配点 : $800$ 点

問題文

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

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

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

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

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

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

制約

• 入力は全て整数
• $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$

出力

答えを出力せよ。

3 7
2 0
3 2
0 3

2

店の回り方の例を $1$ つ示します。

• 時刻 $0$ から時刻 $1$ : 自宅から店 $1$ へ $1$ 単位時間掛けて移動します。
• 時刻 $1$ から時刻 $3$ : 店 $1$ で $2$ 単位時間待ち、買い物をします。
• 時刻 $3$ から時刻 $4$ : 店 $1$ から店 $3$ へ $1$ 単位時間掛けて移動します。
• 時刻 $4$ から時刻 $7$ : 店 $3$ で $3$ 単位時間待ち、買い物をします。

以上の回り方では、時刻 $7.5$ までに $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