Shopping

Time limit1sMemory limit256 MB

Summary

A shopper starts at the entrance, visits each of N shops in a row under the given order constraints, and ends at the exit with the shortest total walk.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals
Solved: No attempts yet

Problem

Your friend goes shopping. The mall runs along a straight street, where $N$ shops numbered 1 to $N$ stand in a row at regular intervals. Each shop has one door, and the distance between the doors of two neighbouring shops is one unit length. The door of shop $k$ is $k$ units from the entrance, and the exit is $N+1$ units from the entrance.

She starts at the entrance, visits all $N$ shops, and finishes at the exit. Visiting a shop means standing at its door and stepping inside.

There are $m$ restrictions on the visiting order. Each restriction is a pair of integers $(c, d)$ with $c < d$ , and it means she must visit shop $c$ after she visits shop $d$ . For example, if she wants to pick a dress before choosing heels, she visits the boutique first and the shoe store later. When the boutique is farther from the entrance than the shoe store, she walks past the door of the shoe store, goes to the boutique, and then walks back to the shoe store.

As long as the visiting order satisfies every restriction, she can visit the remaining shops in any order she likes.

Write a program that computes the minimum walking length she needs to move from the entrance to the exit. Walking inside a shop does not count.

Input

The first line contains two integers $N$ and $m$ , where $N$ is the number of shops and $m$ is the number of restrictions. ( $1 \le N \le 1000$ , $0 \le m \le 500$ )

Each of the next $m$ lines contains one restriction. Line $i$ contains two integers $c_i$ and $d_i$ , meaning she must visit shop $c_i$ after she visits shop $d_i$ . ( $1 \le c_i < d_i \le N$ )

No pair is given twice. That is, there are no distinct $j$ and $k$ with $c_j = c_k$ and $d_j = d_k$ .

Output

Print on one line the minimum walking length she needs to move from the entrance to the exit. Do not count the walking she does inside a shop.

Examples5

Example 1
Input
```
10 3
3 7
8 9
2 5
```
Expected output
```
23
```
Example 2
Input
```
10 3
8 9
6 7
2 4
```
Expected output
```
19
```
Example 3
Input
```
10 0
```
Expected output
```
11
```
Example 4
Input
```
10 6
6 7
4 5
2 5
6 9
3 5
6 8
```
Expected output
```
23
```

Example 5

Input

Expected output