你的朋友喜欢购物。她将沿着一条笔直的街道穿过一个商场，商场内有 $N$ 家商店（编号从 $1$ 到 $N$），它们按规则间隔排列。每家商店都有一个门，位于街道的一侧。相邻商店门之间的距离相等，即为一个单位长度。她从商场入口开始购物，按顺序访问商店购买商品。购物结束后，她必须前往商场的出口。

她对商店的访问顺序有一些限制。每一项限制都指出她必须在访问另一家商店之前先访问某一家商店。例如，当她想在挑选高跟鞋之前买一件漂亮的连衣裙时，她必须在访问鞋店之前先访问精品店。当精品店比鞋店更远时，她必须在访问精品店之前先经过鞋店，并在访问精品店之后再回到鞋店。

只要访问商店的顺序满足所有限制，她可以以任何她喜欢的顺序访问其他商店。

编写一个程序，确定她从入口移动到出口所需的最短步行长度。

假设编号为 $k$ 的商店门的位置距离入口 $k$ 个单位，出口的位置距离入口 $N + 1$ 个单位。

输入格式

输入包含一组测试数据。

$N \ m$ $c_1 \ d_1$ $\vdots$ $c_m \ d_m$

第一行包含两个整数 $N$ 和 $m$，其中 $N$ ($1 \le N \le 1000$) 是商店的数量，$m$ ($0 \le m \le 500$) 是限制的数量。接下来的 $m$ 行中，每一行包含两个整数 $c_i$ 和 $d_i$ ($1 \le c_i < d_i \le N$)，表示第 $i$ 项关于访问顺序的限制，即她必须在访问编号为 $d_i$ 的商店之后，才能访问编号为 $c_i$ 的商店 ($i = 1, \dots, m$)。

不存在满足 $c_j = c_k$ 且 $d_j = d_k$ 的 $j$ 和 $k$ 对。

输出格式

输出她从入口移动到出口所需的最短步行长度。你应该忽略她在商店内部行走的距离。

样例

样例输入 1

10 3
3 7
8 9
2 5

样例输出 1

23

样例输入 2

10 3
8 9
6 7
2 4

样例输出 2

19

样例输入 3

10 0

样例输出 3

11

样例输入 4

10 6
6 7
4 5
2 5
6 9
3 5
6 8

样例输出 4

23

样例输入 5

1000 8
3 4
6 1000
5 1000
7 1000
8 1000
4 1000
9 1000
1 2

样例输出 5

2997