← 返回题目列表

AtCoder · relay2_c

C. 花园

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

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