Monotonically Increasing Tardiness Informatics Tournament (MITIT) の運営ビーバーたちは、コンテストを円滑に運営するために定期的に会議を行う必要がありますが、時折モチベーションを失ってしまうことがあります。

$N$ 匹の運営ビーバーがおり、彼らの会議は毎回ちょうど $M$ 分間続きます。$i$ 番目のビーバーは、最初の会議には $t_i$ 分遅刻して現れます。それ以降の会議では、ビーバー $i$ は前回の会議よりも $a_i$ 分遅く到着します。全員が遅刻し、会議の全時間を逃してしまう最初の会議の回数を出力してください。

あるビーバーが会議の全時間を逃したとは、そのビーバーが $M$ 分以上遅刻して到着したことを指します。

入力

1 行目には、2 つの整数 $N$ ($ 1 \le N \le 2\cdot 10^5$) と $M$ ($ 1 \le M \le 10^9$) が空白区切りで与えられます。

続く $N$ 行の各行には、$i$ 番目のビーバーに関する 2 つの整数 $t_i$ ($0 \le t_i < M$) と $a_i$ ($1 \le a_i \le 10^9$) が与えられます。

出力

答えを 1 行で出力してください。

Example

入力

4 60
0 9
30 4
10 12
14 9

出力

9

注記

最初の会議では、ビーバー 1 は時間通りに到着し、ビーバー 2 は 30 分遅刻し、ビーバー 3 は 10 分遅刻し、ビーバー 4 は 14 分遅刻します。9 回目の会議では、ビーバー 1 は 72 分遅刻し、ビーバー 2 は 62 分遅刻し、ビーバー 3 は 106 分遅刻し、ビーバー 4 は 86 分遅刻します。これが全員が $60$ 分以上遅刻する最初の会議です。8 回目の会議では、ビーバー 2 は 58 分の遅刻となります。