C - Garden

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100

問題

あなたの家の庭には、東に果てしなく伸びる細長い花壇があります。あなたは、何も植えられていないこの花壇に N 種類の花を植えることにしました。便宜上、これらの花の種類を花 1, 2, …, N と呼びます。また、花壇の西端から p センチメートルの位置を位置 p と呼びます。

i (1 ≤ i ≤ N) は、位置 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 番目として数える。)


入力例 1

2 6
20 10
25 15

出力例 1

50

2 種類の花が以下の位置に植えられます。

  • 1: 位置 20, 30, 40, 50, 60,
  • 2: 位置 25, 40, 55, 70, 85,

西から 6 番目の花は、位置 50 に植えられた花 1 です。位置 40 に植えられた 2 本の花を個別に数えていることに注意してください。


入力例 2

3 9
10 10
10 10
10 10

出力例 2

30

位置 10, 20, 30, のそれぞれに花が 3 本ずつ植えられます。したがって、西から 9 番目の花は位置 30 に植えられます。


入力例 3

1 1000000000
1000000000000000000 1000000000

出力例 3

1999999999000000000

Score : 100 points

Problem Statement

In your garden, there is a long and narrow flowerbed that stretches infinitely to the east. You have decided to plant N kinds of flowers in this empty flowerbed. For convenience, we will call these N kinds of flowers Flower 1, 2, …, N. Also, we will call the position that is p centimeters from the west end of the flowerbed Position p.

You will plant Flower i (1 ≤ i ≤ N) as follows: first, plant one at Position w_i, then plant one every d_i centimeters endlessly toward the east. That is, Flower i will be planted at the positions w_i, w_i + d_i, w_i + 2 d_i, Note that more than one flower may be planted at the same position.

Find the position at which the K-th flower from the west is planted. If more than one flower is planted at the same position, they are counted individually.

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ K ≤ 10^9
  • 1 ≤ w_i ≤ 10^{18}
  • 1 ≤ d_i ≤ 10^9
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N K
w_1 d_1
:
w_N d_N

Output

When the K-th flower from the west is planted at Position X, print the value of X. (The westmost flower is counted as the 1-st flower.)


Sample Input 1

2 6
20 10
25 15

Sample Output 1

50

Two kinds of flowers are planted at the following positions:

  • Flower 1: Position 20, 30, 40, 50, 60,
  • Flower 2: Position 25, 40, 55, 70, 85,

The sixth flower from the west is the Flower 1 planted at Position 50. Note that the two flowers planted at Position 40 are counted individually.


Sample Input 2

3 9
10 10
10 10
10 10

Sample Output 2

30

Three flowers are planted at each of the positions 10, 20, 30, Thus, the ninth flower from the west is planted at Position 30.


Sample Input 3

1 1000000000
1000000000000000000 1000000000

Sample Output 3

1999999999000000000