eval"_,K,*A="+`dd`.split*?,
p (1..10**9).bsearch{|i|k=K;A.each_slice(2){|a,b|k-=[0,[b,i].min-a+1].max};k<=0}