eval"N,*L,K="+`dd`.split*?,
p 1e9-(0..1e9).bsearch{|i|L.map{|l|(l./1e9-i).to_i}.sum>=K}