길이가 $N-1$인 수직선이 있다. 수직선 위의 $1$에서 시작하여 $N$에 최단 시간에 도착하는 것을 목표하고 있다. 총 $T$분 동안 매 분마다 통제가 발생한다.

$t$번째 분의 통제는 두 정수 $l_t, r_t$로 주어지며, $t+0.5$분에 에 당신의 위치 $x$가 $(l_t \le x \le r_t)$를 만족하면 즉시 실패하게 된다. $T < t$라면 아무런 통제가 발생하지 않는다.

매 분 인접한 칸으로 이동하거나 현재 칸에 머무를 수 있다. $N$에 도달한 즉시 목표에 성공한다.

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

Input

첫 번째 줄에 수직선의 길이 $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)$

Output

최단 시간을 출력한다. 존재하지 않으면 -1을 출력한다.

Examples

Input 1

4
4
2 4
1 1
2 2
3 3

Output 1

4

Input 2

5
3
2 5
3 4
1 4

Output 2

-1