20905번 - Exhausting Errands 다국어

문제

Dolly the delivery drone is out for a busy working day. It has to complete $n$ errands in a street where $\ell$ houses are lined up in a row, numbered in ascending order as 1,ドル \dots, \ell$. The distance between adjacent houses is 1ドル$. Each errand consists of picking up a package at some house $a$ and delivering it to another house $b$. Dolly can start with any errand, complete the errands in any order, and is able to carry an unlimited number of packages at the same time. Your job is to find the minimal total distance Dolly has to cover to complete all errands. The delivery route can start and finish at arbitrary locations along the street.

Figure E.1: Illustration of Sample Input 1. The shortest route is 2ドル \rightarrow 1 \rightarrow 9 \rightarrow 4$ with length 14ドル$.

입력

The input consists of:

• One line with two integers $\ell$ and $n$ (1ドル \le \ell \le 10^9,ドル 1ドル \le n \le 10^5$), where $\ell$ is the number of houses in the street, and $n$ is the number of errands.
• $n$ lines, each with two integers $a$ and $b$ (1ドル \le a, b \le \ell$ with $a \not= b$) describing an errand where a package must be picked up at house $a$ and be delivered to house $b$.

출력

Output a single line with the minimal distance Dolly has to cover from picking up the first package until delivering the last package.

제한

힌트