#512. 曹冲养猪

曹冲养猪

题目描述

自从曹冲搞定了大象以后,曹操就开始琢磨让儿子干些事业,于是派他到中原养猪场养猪,可是曹冲很不高兴,于是在工作中马马虎虎,有一次曹操想知道母猪的数量,于是曹冲想狠狠耍曹操一把。

举个例子,假如有 1616 头母猪,如果建了 33 个猪圈,剩下 11 头猪就没有地方安家了;如果建造了 55 个猪圈,但是仍然有 11 头猪没有地方去;如果建造了 77 个猪圈,还有 22 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总,你该怎么办?

输入格式

第一行包含一个整数 nn,表示建立猪圈的次数;

接下来 nn 行,每行两个整数 ai,bia_i, b_i,表示建立了 aia_i 个猪圈,有 bib_i 头猪没有去处。你可以假定 ai,aja_i,a_j 互质。

输出格式

输出仅包含一个正整数,即为曹冲至少养猪的数目。

样例

3
3 1
5 1
7 2
16

数据范围与提示

对于全部数据,1n10,1biai10001\le n\le 10,1\le b_i\le a_i\le 1000