Minimum Walking Distance for Shop Deliveries

There are l shops on a street, numbered from 1 to l from west to east, with adjacent shops 1 meter apart. You are given n tasks; the i-th task requires moving goods from shop s_i to shop t_i. You can carry an arbitrarily heavy load in one go, and you are allowed to start at any shop and finish at any shop after completing all tasks. For each task, you must physically travel from s_i to t_i along the street.

Since tasks can be performed in any order and you can carry multiple items at once, the problem reduces to planning your route optimally. Notice that if a task requires you to go eastward (i.e. s_i ≤ t_i), then you only need to cover the interval from the minimum pickup location to the maximum delivery location among all eastward tasks. Similarly, if a task is westward (i.e. s_i > t_i), then you only need to cover the interval from the maximum pickup location to the minimum delivery location among all westward tasks. The answer is the sum of these two distances (if such tasks exist).

Formally, let \[ \text{east_range} = \begin{cases} \max_{s_i\le t_i} (t_i) - \min_{s_i\le t_i} (s_i) & \text{if there is at least one eastward task},\\ 0 & \text{otherwise}, \end{cases} \] \[ \text{west_range} = \begin{cases} \max_{s_i> t_i} (s_i) - \min_{s_i> t_i} (t_i) & \text{if there is at least one westward task},\\ 0 & \text{otherwise}. \end{cases} \] Then the minimum total walking distance is \[ \text{answer} = \text{east_range} + \text{west_range}. \]

Your task is to compute the minimum total walking distance required to complete all deliveries.

inputFormat

The first line contains two integers l and n (1 ≤ l ≤ 10⁹, 1 ≤ n ≤ 10⁵), representing the number of shops and the number of tasks, respectively.

Each of the next n lines contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ l), indicating that goods need to be moved from shop s_i to shop t_i.

outputFormat

Output a single integer: the minimum total distance you must walk to complete all tasks.

sample

10 2
3 1
6 8

4