AT_relay2_c.Garden

你的家的院子里，有一条向东无限延伸的细长花坛。你打算在这条什么都没种的花坛上种下 $N$ 种花。为方便起见，将这些花的种类分别称为花 $1$，$2$，……，$N$。另外，我们把距离花坛西端 $p$ 厘米的位置称为位置 $p$。

对于花 $i$（$1 \leq i \leq N$），你会在位置 $w_i$ 上种下一株，然后每隔 $d_i$ 厘米，继续向东不断地种下一株。也就是说，花 $i$ 会被种在位置 $w_i$，$w_i + d_i$，$w_i + 2d_i$，……。多个花可能会被种在同一个位置。

请你求出从西边数起第 $K$ 朵被种下的花所在的位置。如果同一个位置上种下了多朵花，它们需要分别计数。

输入以如下格式从标准输入读入：

$N$ $K$ $w_1$ $d_1$ $w_2$ $d_2$ … $w_N$ $d_N$

若从西边数起第 $K$ 朵被种下的花在位置 $X$，请输出 $X$ 的值。（注意，将最西边的花视为第 $1$ 朵。）

限制条件

• $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$
• 输入均为整数。

样例解释 1

有 $2$ 种花分别被种在以下位置：

• 花 $1$：位置 $20$、$30$、$40$、$50$、$60$、……
• 花 $2$：位置 $25$、$40$、$55$、$70$、$85$、……

从西边数起第 $6$ 朵花是种在位置 $50$ 的花 $1$。请注意，种在位置 $40$ 的两朵花需分别计数。

样例解释 2

在位置 $10$、$20$、$30$、…… 上，各有 $3$ 朵花。因此，从西边数起第 $9$ 朵花位于位置 $30$。

由 ChatGPT 5 翻译