END { load __FILE__ unless $stdin.eof? }

h, w = gets.split.map!(&:to_i)

tbl = Array.new(w + 1, 0)
tbl[0] = 999999

hmax = h.times do |j|
  a, b = gets.split.map!(&:to_i)
  (a..b).each { |i| tbl[i] = 999999 }
  prev = 999999
  tbl.map! { |x| prev = [prev, x].min + 1 }

  smin = tbl.min
  break j if smin >= 999999
  puts smin
end

(h - hmax).times { puts -1 }
