#P18854. [Croatian CPC2024] Jaki Jovsi

[Croatian CPC2024] Jaki Jovsi

Jaki Jovsi

题目描述

一条直街上有 ll 家酒馆,从街的一端到另一端依次编号为 11 到 ll。相邻两家酒馆之间的距离恰好为 11 米。

Jovsi 要完成 nn 个送货任务。第 ii 个任务要求他在酒馆 aia_i 取走一个包裹,并把它送到酒馆 bib_i。

任务可以按任意顺序完成,且 Jovsi 可以同时携带任意数量的包裹。他可以任选一家酒馆开始路线,也可以任选一家酒馆结束路线,不需要为到达起点或离开终点付出路程。

求完成所有任务所需行走的最短总距离。

输入格式

第一行包含两个整数 l,nl,n(1≤l≤1091\le l\le10^9,1≤n≤1051\le n\le10^5)。

接下来 nn 行,第 ii 行包含两个整数 ai,bia_i,b_i(1≤ai,bi≤l1\le a_i,b_i\le l,ai≠bia_i\ne b_i),描述第 ii 个任务。

输出格式

输出一个整数,表示最短总距离。

样例输入 1

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

样例输出 1

14

样例输入 2

100 3
11 50
50 49
36 35

样例输出 2

42

样例解释

第一个样例可以从酒馆 22 出发,依次经过酒馆 1,3,4,5,6,7,8,9,5,41,3,4,5,6,7,8,9,5,4。经过各酒馆时取走或交付对应包裹,最终在酒馆 44 结束,行走总距离为 1414 米。