쇼핑

시간 제한1초메모리 제한256 MB

요약

입구에서 출발해 주어진 순서 제약을 지키며 일렬로 늘어선 N개 상점을 모두 방문하고 출구에 도착하는 가장 짧은 이동 거리를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 구간
정답자: 아직 제출이 없습니다

문제

친구가 쇼핑을 하러 간다. 쇼핑몰은 곧게 뻗은 거리를 따라 놓여 있고, 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$ 는 없다.

출력

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

예제5

예제 1
입력
```
10 3
3 7
8 9
2 5
```
예상 출력
```
23
```
예제 2
입력
```
10 3
8 9
6 7
2 4
```
예상 출력
```
19
```
예제 3
입력
```
10 0
```
예상 출력
```
11
```
예제 4
입력
```
10 6
6 7
4 5
2 5
6 9
3 5
6 8
```
예상 출력
```
23
```

예제 5

입력

예상 출력