쇼핑

친구가 쇼핑을 하러 간다. 쇼핑몰은 곧게 뻗은 거리를 따라 놓여 있고, 1번부터 $N$번까지 번호가 붙은 가게 $N$개가 같은 간격으로 한 줄로 늘어서 있다. 가게마다 문이 하나씩 있고, 이웃한 두 가게의 문 사이 거리는 모두 단위 길이 1이다. $k$번 가게의 문은 입구에서 $k$만큼 떨어진 곳에 있고, 출구는 입구에서 $N+1$만큼 떨어진 곳에 있다.

친구는 입구에서 출발해 가게 $N$개를 모두 방문하고 출구에서 쇼핑을 끝낸다. 가게를 방문한다는 것은 그 가게의 문 앞에 서서 안으로 들어간다는 뜻이다.

방문 순서에는 제약이 $m$개 있다. 각 제약은 $c < d$인 정수 쌍 $(c, d)$이고, $d$번 가게를 방문한 뒤에 $c$번 가게를 방문해야 한다는 뜻이다. 예를 들어 드레스를 고른 다음에 구두를 고르고 싶다면 옷 가게를 먼저 방문하고 신발 가게를 나중에 방문한다. 옷 가게가 신발 가게보다 입구에서 멀면 신발 가게 문 앞을 그냥 지나쳐 옷 가게까지 갔다가, 다시 신발 가게로 되돌아와야 한다.

제약을 모두 지키기만 하면 나머지 가게는 원하는 순서대로 방문해도 된다.

입구에서 출구까지 이동하는 데 필요한 최소 걷기 길이를 구하는 프로그램을 작성하라. 가게 안에서 걷는 거리는 세지 않는다.

첫째 줄에 정수 $N$과 $m$이 주어진다. $N$은 가게의 수이고 $m$은 제약의 수이다. ($1 \le N \le 1000$, $0 \le m \le 500$)

다음 $m$개 줄에 제약이 한 줄에 하나씩 주어진다. $i$번째 줄에는 정수 $c_i$와 $d_i$가 주어지며, $d_i$번 가게를 방문한 뒤에 $c_i$번 가게를 방문해야 한다는 뜻이다. ($1 \le c_i < d_i \le N$)

같은 쌍이 두 번 주어지지는 않는다. 즉 $c_j = c_k$이면서 $d_j = d_k$인 서로 다른 $j$와 $k$는 없다.

입구에서 출구까지 이동하는 최소 걷기 길이를 한 줄에 출력한다. 가게 안에서 걷는 거리는 세지 않는다.