시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB80262231.429%

문제

길이가 $N-1$인 수직선이 있다. 수직선 위의 $1$에서 시작하여 $N$에 가능한 한 빠르게 도달하는 것이 목표이다.

시각 $0$분에 시작해서 매 분마다 $1$분에 걸쳐 다음 세 행동 중 하나를 할 수 있다.

  • 현재 위치에서 왼쪽으로 $1$만큼 이동한다.
  • 현재 위치에서 오른쪽으로 $1$만큼 이동한다.
  • 현재 위치에 그대로 머문다.

단, 이동한 뒤의 위치는 항상 $1$ 이상 $N$ 이하여야 한다. $N$에 도착하는 즉시 성공한 것으로 간주한다.

$1$분부터 $T$분까지 총 $T$분 동안 매 분마다 통제가 발생한다. $t$분의 통제는 두 정수 $l_t, r_t$로 주어지며, 시각 $t$분에 이동을 모두 마친 직후 당신의 위치 $x$가 $l_t \le x \le r_t$를 만족하면 즉시 실패한다. $T < t$인 경우에는 통제가 발생하지 않는다.

실패하지 않고 $N$에 도착하는 방법이 존재한다면 가능한 최단 시간을 출력하고, 존재하지 않으면 -1을 출력하시오.

입력

첫 번째 줄에 도착 지점 $N$이 주어진다. $(1 \le N \le 2 \times 10^5)$

두 번째 줄에 통제가 발생하는 총 시간 $T$가 주어진다. $(1 \le T \le 2 \times 10^5)$

세 번째 줄부터 $T$개의 줄에 걸쳐 각 줄에 두 정수 $l_t$, $r_t$가 공백으로 구분되어 주어진다.$(1 \le l_t \le r_t \le N)$

출력

실패하지 않고 좌표 $N$에 도달할 수 있다면 가능한 최단 시간을 출력한다.

그러한 방법이 존재하지 않으면 -1을 출력한다.

예제 입력 1

4
4
2 4
1 1
2 2
3 3

예제 출력 1

4

예제 입력 2

5
3
2 5
3 4
1 4

예제 출력 2

-1