题目描述

送货无人机 Dolly 正在度过忙碌的一天。它需要在一条街道上完成 $n$ 项差事。这条街上有 $\ell$ 栋房屋，按照从左到右的顺序编号为 $1,2,\ldots,\ell$，相邻两栋房屋之间的距离为 $1$。

每项差事都要求 Dolly 在某栋房屋 $a$ 取走一个包裹，并把它送到另一栋房屋 $b$。

Dolly 可以：

• 从任意一项差事开始；
• 以任意顺序完成所有差事；
• 同时携带任意数量的包裹。

请计算 Dolly 完成全部差事所需行驶的最小总距离。路线可以从街道上的任意位置开始，也可以在任意位置结束。

上图为样例 1。最短路线之一为 $2\to1\to9\to4$，总长度为 $14$。

输入格式

第一行包含两个整数 $\ell$ 和 $n$：

• $\ell$（$1\le \ell\le 10^9$）表示街道上的房屋数量；
• $n$（$1\le n\le 10^5$）表示差事数量。

接下来 $n$ 行，每行包含两个整数 $a,b$（$1\le a,b\le \ell$ 且 $a\ne b$），表示一项差事：需要在房屋 $a$ 取走包裹，并将其送到房屋 $b$。

输出格式

输出一个整数，表示 Dolly 从取走第一个包裹开始，到送达最后一个包裹为止所需行驶的最小距离。

样例 1

输入

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

输出

14

样例 2

输入

100 3
11 50
50 49
36 35

输出

42