f=->(w){a,b=A.map{|a,b|a+b*w}.minmax;b-a}
A=$<.drop(1).map{|e|e.split.map &:to_i}
l=1
r=1<<30
f[x=(l*2+r)/3]<=f[y=(l+r*2)/3] ? r=y : l=x while l+2<r
p (l..r).min_by(&f)