分数: 100 点
问题陈述
在你的花园里,有一个狭长的花坛,向东无限延伸。你决定种植 N 这个空花坛里有各种各样的花。为了方便起见,我们将这些称为 N 种花 花 1, 2, …, N。另外,我们将调用该位置 p 距花坛西端厘米位置 p.
你会种花 i (1 ≤ i ≤ N) 如下:首先,在Position处种植一个 w_i,然后每隔 d_i 厘米无尽地向东。也就是花 i 将被种植在这些位置 w_i, w_i + d_i, w_i + 2 d_i, … 请注意,同一位置可以种植多于一朵花。
查找 K种植了西边的第朵花。如果同一位置种植多于一朵花,则单独计数。
约束
- 1 ≤ N ≤ 10^5
- 1 ≤ K ≤ 10^9
- 1 ≤ w_i ≤ 10^{18}
- 1 ≤ d_i ≤ 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K w_1 d_1 : w_N d_N
输出
当 K西数第 朵花种植在 位置 X,打印值 X。 (最西边的花算作 1-st花。)
示例输入 1
2 6 20 10 25 15
示例输出 1
50
两种花卉种植在以下位置:
- 花 1:位置 20, 30, 40, 50, 60, …
- 花 2:位置 25, 40, 55, 70, 85, …
西数第六朵花是花 1 种植在 位置 50。请注意,这两朵花种植在位置 40 单独计数。
示例输入 2
3 9 10 10 10 10 10 10
示例输出 2
30
每个位置种植三朵花 10, 20, 30, … 因此,从西数第九朵花种植在位置 请回答下面的 30.
示例输入 3
1 1000000000 1000000000000000000 1000000000
示例输出 3
1999999999000000000