C - 植物の成長観察 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は学校の理科の授業で、 N 種類の植物を育てる実験を行っています。

それぞれの植物は、実験開始時の高さと、1日あたりの成長量が異なります。具体的には、 i 番目の植物（ 1 \leq i \leq N ）は、実験開始時（ 0 日目）の高さが A_i cm であり、1日あたり B_i cm ずつ成長します。すなわち、 d 日目（ d = 0, 1, 2, \ldots ）における i 番目の植物の高さは A_i + B_i \times d cm です。

高橋君は 0 日目, 1 日目, 2 日目, \ldots と毎日植物の高さを確認し、すべての植物の高さが M cm 以上になった最初の日に観察を終了する計画です。

観察が終了する日、すなわち、すべての i （ 1 \leq i \leq N ）について A_i + B_i \times d \geq M が成り立つような最小の非負整数 d を求めてください。

なお、制約の条件のもとで、答えは必ず有限の値として存在します。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数である

入力

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、植物の種類数を表す整数 N と、目標の高さを表す整数 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（ 1 \leq i \leq N ）には、 i 番目の植物の実験開始時の高さ A_i と、1日あたりの成長量 B_i が、スペース区切りで与えられる。

出力

すべての植物の高さが M cm 以上となる最小の非負整数 d を 1 行で出力せよ。

入力例 1

3 10
2 3
5 2
8 1

出力例 1

3

入力例 2

4 100
100 5
90 10
95 3
80 4

出力例 2

5

入力例 3

5 1000000000
1 1
500000000 100000000
999999999 1
100000000 300000000
250000000 250000000

出力例 3

999999999

Score : 300 pts

Problem Statement

Takahashi is conducting an experiment growing N types of plants in his school science class.

Each plant has a different initial height and daily growth rate. Specifically, the i-th plant (1 \leq i \leq N) has a height of A_i cm at the start of the experiment (day 0) and grows by B_i cm per day. That is, the height of the i-th plant on day d (d = 0, 1, 2, \ldots) is A_i + B_i \times d cm.

Takahashi plans to check the heights of the plants every day on day 0, day 1, day 2, \ldots, and end the observation on the first day when all plants have a height of at least M cm.

Find the day when the observation ends, that is, the smallest non-negative integer d such that A_i + B_i \times d \geq M holds for all i (1 \leq i \leq N).

Note that under the given constraints, the answer is guaranteed to exist as a finite value.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All input values are integers

Input

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of plant types and an integer M representing the target height, separated by a space.
  • The following N lines each contain, for the i-th line (1 \leq i \leq N), the initial height A_i and the daily growth rate B_i of the i-th plant, separated by a space.

Output

Print on a single line the smallest non-negative integer d such that all plants have a height of at least M cm.

Sample Input 1

3 10
2 3
5 2
8 1

Sample Output 1

3

Sample Input 2

4 100
100 5
90 10
95 3
80 4

Sample Output 2

5

Sample Input 3

5 1000000000
1 1
500000000 100000000
999999999 1
100000000 300000000
250000000 250000000

Sample Output 3

999999999