//working_memory=128MB

int @n;
ll @k;
int @a[n],@b[n];
ull c[n*128+1];
int cn=0;

rep(i,n){
	ll d[128],e[128];
	int dn=Divisor(a[i],d);
	rep(j,dn){
		e[j]=(-b[i])%%d[j];
	}
	ll t=e[dn-1];
	k-=t;
	rrep(j,dn-1){
		if(t>e[j]){
			c[cn++]=(ull)d[j]<<32|t-e[j];
			t=e[j];
		}
	}
}

sortA(cn,c);
c[cn]=(ll)int_inf<<32;

while(k<0){
	ull v=c[--cn];
	k+=(int)v;
}

wt(min(c[cn]>>32,a(n)));