#P16605. [GCPC2020]Exhausting Errands

[GCPC2020]Exhausting Errands

题目描述

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

每项差事都要求 Dolly 在某栋房屋 aa 取走一个包裹,并把它送到另一栋房屋 bb。

Dolly 可以:

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

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

上图为样例 1。最短路线之一为 2→1→9→42\to1\to9\to4,总长度为 1414。

输入格式

第一行包含两个整数 ℓ\ell 和 nn:

  • ℓ\ell(1≤ℓ≤1091\le \ell\le 10^9)表示街道上的房屋数量;
  • nn(1≤n≤1051\le n\le 10^5)表示差事数量。

接下来 nn 行,每行包含两个整数 a,ba,b(1≤a,b≤ℓ1\le a,b\le \ell 且 a≠ba\ne b),表示一项差事:需要在房屋 aa 取走包裹,并将其送到房屋 bb。

输出格式

输出一个整数,表示 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