分箱余量还原

普及-⏱ 1000ms💾 256MB#P3267🏷️ 中国剩余定理扩展欧几里得数论

题目描述

一批货物被多次尝试装进等容量箱子:第 $i$ 次用容量为 $a_i$ 的箱子装完后余下 $b_i$ 件装不下。 已知各次容量 $a_i$ 两两互质,求货物总数的最小可能值(正整数)。

输入格式

第一行一个整数 $n$($n \le 10$)。 接下来 $n$ 行每行两个整数 $a_i, b_i$($1 \le b_i < a_i$,各 $a_i$ 两两互质)。

输出格式

一行一个正整数:货物总数的最小可能值。

数据范围

None

样例输入 #1
3
3 1
5 1
7 2
样例输出 #1
16
样例输入 #2
1
10 3
样例输出 #2
3