H, W = gets.split.map(&:strip).map(&:to_i)
A = Array.new(H)
B = Array.new(H)
H.times do |i|
  A[i], B[i] = gets.split.map(&:strip).map(&:to_i)
end

@m = {}
def solve(k)
  def ssolve(k, w)
    if k == 0
      return 0
    end
    if !@m[k].nil? && !@m[k][w].nil?
      return @m[k][w]
    end
    if A[k-1] <= w && w <= B[k-1]
      ay = 0
    else
      ay = ssolve(k-1,w) + 1
    end
    if w == 1
      if ay > 0
        a = ay
      else
        a = -1
      end
    else
      ax = ssolve(k, w-1) + 1
      if ax > 0
        if ay > 0
          a = [ax, ay].min
        else
          a = ax
        end
      else
        if ay > 0
          a = ay
        else
          a = -1
        end
      end
    end

    @m[k] ||= {}
    @m[k][w] = a
    return a
  end

  ma = 10**6
  (1..W).each do |w|
    a = ssolve(k,w)
    if a > 0 && a < ma
      ma = a
    end
  end
  ma != 10**6 ? ma : -1
end

(1..H).each do |k|
  puts solve(k)
end
