题目描述

あなたの家の庭には、東に果てしなく伸びる細長い花壇があります。あなたは、何も植えられていないこの花壇に $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$ 番目に植えられる花の位置を求めてください。なお、同じ位置に複数の花が植えられる場合、それらは個別に数えます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $w_1$ $d_1$ $:$ $w_N$ $d_N$

输出格式

西から $K$ 番目に植えられる花の位置が位置 $X$ であるとき、$X$ の値を出力せよ。（最も西に植えられる花を $1$ 番目として数える。）

题目大意

你要在一个向东延伸的花坛中种 $N$ 种花，称距离花坛西端 $p$ 厘米的位置为 $p$ 位置。

对于第 $i$ 种花，在位置 $w_i$ ， $w_i+d_i$ ， $w_i+2d_i$ …… 位置种花。一个位置可以种多种花。

请输出从西边开始数第 $K$ 朵花的位置。

2 6
20 10
25 15

50

3 9
10 10
10 10
10 10

30

1 1000000000
1000000000000000000 1000000000

1999999999000000000

提示

制約

• $1\ <\ =\ N\ <\ =\ 10^5$
• $1\ <\ =\ K\ <\ =\ 10^9$
• $1\ <\ =\ w_i\ <\ =\ 10^{18}$
• $1\ <\ =\ d_i\ <\ =\ 10^9$
• 入力値はすべて整数である。

Sample Explanation 1

$2$ 種類の花が以下の位置に植えられます。 - 花 $1$: 位置 $20,$ $30,$ $40,$ $50,$ $60,$ $…$ - 花 $2$: 位置 $25,$ $40,$ $55,$ $70,$ $85,$ $…$ 西から $6$ 番目の花は、位置 $50$ に植えられた花 $1$ です。位置 $40$ に植えられた $2$ 本の花を個別に数えていることに注意してください。

Sample Explanation 2

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