分数: 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