题目描述

工厂有 $n$ 台独立工作的机器。第 $i$ 台机器在第 $s_i$ 秒完成它的第一件产品，此后每隔 $t_i$ 秒再完成一件产品。所有机器从第 $0$ 秒开始运行。

请计算所有机器合计完成至少 $m$ 件产品的最早时刻。

输入格式

第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行输入两个整数 $s_i,t_i$。

输出格式

输出一个整数，表示最早完成至少 $m$ 件产品的时刻（单位：秒）。

样例

2 5
2 3
4 2

8

数据规模与约定

• $1\le n\le2\times10^5$；
• $1\le m\le10^9$；
• $1\le s_i,t_i\le10^9$；
• 保证答案不超过 $10^{18}$。