int@n,@k,@a[n],@b[n];
int dn[n],dd[n][128],e[][];

rep(i,n){
	dn[i]=Divisor(a[i],dd[i]);
	rep(j,dn[i]){
		e[i][j]=(-b[i])%%dd[i][j];
	}
	rrep(j,dn[i]-1){
		chmin(e[i][j],e[i][j+1]);
	}
}

int l=1,h=min(a(n))+1;
while(l+1<h){
	int m=l+h>>1;
	int z=0;
	rep(i,n){
		int j=bsearch_min[int,j,0,dn[i]](dd[i][j]>=m);
		z+=e[i][j];
	}
	(z>k?h:l)=m;
}
wt(l);