program i_hate_shortest_path_problem
  implicit none
  integer, parameter :: inf = 1e9
  integer :: h, w, a, b, m, i, j
  integer, allocatable :: x(:)
  read(*,*) h, w
  allocate(x(w))
  x = [(i, i = 1, w)]
  do i = 1, h
    read(*,*) a, b
    where (a <= x .and. x <= b)
      x = b + 1
    end where
    m = inf
    do j = 1, w
      if (x(j) <= w) m = min(m, x(j) + i - j)
    end do
    write(*,'(i0)') merge(-1, m, m == inf)
  end do
end program i_hate_shortest_path_problem