Bessie’s Taxi Detour

Bessie runs a taxi service along a fence of length \(M\) (where \(1 \le M \le 10^9\)). There are \(N\) cows (with \(1 \le N \le 10^5\)) waiting at various locations. Each cow has a pickup location \(a_i\) and a destination \(b_i\). Bessie must transport every cow from its pickup to its destination, but her car can only hold one cow at a time. Moreover, in order to save gas, Bessie is allowed to drop a cow off at a point that is different from its specified destination if that helps her combine trips and reduce extra travel.

Bessie starts at position 0 (the leftmost point of the fence) and must finish at position \(M\) (the rightmost point). When a cow’s desired direction is the same as the taxi’s main direction (i.e. when \(a_i \le b_i\)), Bessie can serve the cow as she naturally moves from 0 to \(M\> without any extra distance. However, if a cow’s pickup is to the right of its destination (i.e. \(a_i > b_i\)), then serving that cow requires a detour: Bessie must drive forward to the pickup and then backtrack in order to drop the cow off. In an optimal schedule, Bessie can merge overlapping detours. In other words, if two or more cows require backward transport, their detour segments (defined by the interval \([b_i, a_i]\)) can be merged, and the extra distance incurred is twice the total length of the union of these intervals.

Your task is to compute the minimum distance Bessie must drive. This is equal to the length of the main route (i.e. \(M\)) plus the extra detour distance. Formally, if the union of all intervals \([b_i, a_i]\) over all cows with \(a_i > b_i\) has total length \(L\), then the answer is

[ \text{answer} = M + 2 \cdot L. ]

Input Format: The first line contains two integers \(M\) and \(N\). Each of the next \(N\) lines contains two integers \(a_i\) and \(b_i\) representing the pickup and destination positions respectively.

Note: Cows for which \(a_i \le b_i\) do not force any detour because they can be served along the main route from 0 to \(M\>. However, for cows with \(a_i > b_i\) the taxi must deviate from the main route. An optimal solution is obtained by merging all overlapping intervals \([b_i, a_i]\) for those cows and adding twice their total length to \(M\>.

inputFormat

The first line contains two space‐separated integers \(M\) and \(N\). Then \(N\) lines follow, each containing two space‐separated integers \(a_i\) and \(b_i\), representing the pickup and destination positions of a cow.

\(1 \le M \le 10^9\), \(1 \le N \le 10^5\), and \(0 \le a_i, b_i \le M\).

outputFormat

Output a single integer: the minimum total distance Bessie must drive to transport all cows, starting at 0 and ending at \(M\>.

sample

10 2
8 3
7 5

20