U102583.小蠢等公交1

小蠢在公交站等车，车站有多条公交线路，每条线路的公交车以固定的间隔发车。小蠢可以在任意时刻到达车站，他想知道自己最少需要等待多长时间才能坐上任意一辆公交车。

题目描述：​

给定 $n$ 条公交线路，每条线路有两个参数：
发车间隔 $t_i$ （分钟）
从当前时刻到下一班车到达的剩余时间 $r_i$ （分钟）（保证 $0≤r_i<t_i$）
小蠢可以在任意整数分钟时刻到达车站（从时刻 0 开始计算），到达后，如果当前时刻恰好有公交车到站，他可以立即上车；否则需要等待到下一班车到达。
请帮助小蠢选择一个到达时刻，使得他的等待时间最少，并输出这个最短等待时间。

第一行一个整数 $n$ （$1≤n≤10^5$）
接下来 $n$ 行，每行两个整数 $t_i , r_i$ （$1≤t_i≤10^9 ，0≤r_i≤t_i$）

一个整数，表示最短等待时间。

样例解释：​

• 线路1：发车间隔5分钟，当前下一班车在2分钟后到达。
• 线路2：发车间隔6分钟，当前下一班车在4分钟后到达。
• 线路3：发车间隔7分钟，当前下一班车在3分钟后到达。
  如果小蠢在时刻1到达：
• 线路1下一班车在时刻2（等待1分钟）
• 线路2下一班车在时刻4（等待3分钟）
• 线路3下一班车在时刻3（等待2分钟）
  他可以坐上线路1的车，等待时间为1分钟。
  可以证明没有等待时间更短的方案，因此输出1。

---

数据范围：​

对于 30% 的数据，$n≤1000，t_i≤1000$
对于 100% 的数据，$n≤10^5，t_i≤10^9$

---

提示：​

注意：小蠢到达时刻可以是任意非负整数，包括0。
对于每条线路，如果小蠢在时刻 x到达，那么下一班车的到达时刻是：
如果 $x≤r_i$，则到达时刻为 $r_i$；
如果 $x>r_i$，则到达时刻为 $r_i+k·t_i$​，其中 $k$ 是最小的非负整数使得 $r_i+k·t_i≥x$。

---

本题核心是贪心思想：实际上不需要枚举所有到达时刻，只需要考虑每个 $r_i$以及 $r_i-1$ 等有限个关键时刻即可。