← 返回题目列表

AtCoder · awc0002_c

C. 观察植物生长

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在进行一项种植实验 N 他学校科学课上的植物类型。

每种植物都有不同的初始高度和每日生长速度。具体来说, i第工厂(1 \leq i \leq N) 的高度为 实验开始时的 A_i cm(天 0)并增长 B_i 厘米每天。也就是说,高度 i当天第 1 株植物 d (d = 0, 1, 2, \ldots)是 A_i + B_i \times d 厘米。

高桥计划每天检查植物的高度 0,日 1,日 2, \ldots,并在第一天所有植物的高度至少为 M 厘米。

求观察结束的日期,即最小的非负整数 d 这样 A_i + B_i \times d \geq M 适用于所有 i (1 \leq i \leq N).

请注意,在给定的约束下,答案保证作为有限值存在。

约束

  • 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
  • 第一行包含一个整数 N 代表植物类型的数量和一个整数 M 代表目标高度,以空格分隔。
  • 以下 N 行各包含,对于 i- 第行 (1 \leq i \leq N), 初始高度 A_i 和日增长率 B_i 的 i第一个植物,以空格分隔。

输出

在单行上打印最小的非负整数 d 使得所有植物的高度至少为 M 厘米。


示例输入 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