配点 : $100$ 点

問題

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

花 $i$ $(1 \leq i \leq N)$ は、位置 $w_i$ に一つ植え、そこから $d_i$ センチメートルおきに一つずつ、東へと無数に植えていくことにします。 すなわち、花 $i$ は位置 $w_i,$ $w_i + d_i,$ $w_i + 2 d_i,$ $\cdots$ に植えられることになります。 複数の花が同じ位置に植えられることもありえます。

西から $K$ 番目に植えられる花の位置を求めてください。なお、同じ位置に複数の花が植えられる場合、それらは個別に数えます。

制約

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

入力

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

$N$ $K$

$w_1$ $d_1$

$:$

$w_N$ $d_N$

出力

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

2 6
20 10
25 15

50

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

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

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

3 9
10 10
10 10
10 10

30

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

1 1000000000
1000000000000000000 1000000000

1999999999000000000