Metro Ticket Swapping Minimization

In Wuhan, the metro ticket system charges based on the station at which a passenger enters and the station at which they exit. The cost is defined as \( cost(i,j)=|i-j| \), where \( i \) is the entry station and \( j \) is the exit station. A group of \( n \) people, numbered \( 1, \dots, n \), wishes to travel on a single straight metro line with \( m \) stations labeled \( 1,2,\dots,m \). The \( i\)-th person starts at station \( s_i \) and travels to station \( e_i \) along the shortest path. Note that if \( s_i e_i \) then the route is \( s_i, s_i-1, \dots, e_i \).

Each person initially uses a "Wuhan Pass" (a transit card) that records their starting station \( s_i \). When exiting at station \( e_i \), they are charged \( |ticket\_start - e_i| \). However, passengers are allowed to change their travel plan using the following two operations as many times as desired, provided that after all operations each person exits at their intended destination:

• Operation 0 x y: Person \( x \) rides the metro from their current station to station \( y \). The move must be toward the destination \( e_x \) (i.e. cannot move in the opposite direction) and \( y \) must be different from the current station.
• Operation 1 x y: Two persons \( x \) and \( y \) (currently at the same station) exchange their Wuhan Passes.

Because the charging is independent of the travel duration, clever passengers can swap their passes en route so that when they exit the system the recorded entry station on their pass is as close as possible to their exit station. In the ideal scenario, if two travelers have overlapping travel segments, they can swap the cards and reduce the overall fee. For example, if person 1 travels from station A to station B and person 2 from station B to station A, by meeting at an intermediate station they can exchange passes and both pay \(0\) cost.

More generally, given \( n \) persons, each with an interval defined by \( [min(s_i, e_i), max(s_i,e_i)] \), a swap is allowed only when the paths of the involved persons intersect. In each connected group (where every pair of travels is linked by overlapping intervals) the passes can be arbitrarily reassigned among the group. The minimal total cost is thus achieved by, within each connected component, sorting the original starting stations and the exit stations separately and matching them in order (which minimizes the sum of absolute differences).

Your task is to compute the minimal possible total cost charged on all Wuhan Passes after the passengers plan their journey optimally.

Input Format: The metro line has \( m \) stations and there are \( n \) passengers. Each passenger takes the shortest path from \( s_i \) to \( e_i \) (with \( s_i \neq e_i \)).

Note: If two intervals do not overlap, the passengers cannot swap passes and must pay the natural cost \( |s_i-e_i| \). Otherwise, in a connected set of overlapping journeys, the optimal cost is obtained by summing \( |s'_i - e'_i| \) over the sorted sequences of starting stations \( s'_i \) and destination stations \( e'_i \) in that group.

inputFormat

The first line contains two integers \( m \) and \( n \) (the number of stations and the number of passengers, respectively).

Each of the following \( n \) lines contains two integers \( s_i \) and \( e_i \) indicating the starting and destination stations for the \( i\)-th passenger. It is guaranteed that \( s_i \neq e_i \) and that the passenger always travels along the shortest path.

outputFormat

Print one integer: the minimal total cost (the sum of fees charged on all Wuhan Passes) possible if the passengers swap passes optimally.

sample

10 2
3 7
7 3

0