K,*A=$<.map{|e|e.split.map &:to_i}
p (1..10**9).bsearch{|i|A.map{|a,b|[0,[b,i].min-~-a].max}.sum>=K[1]}