Au 国的 Au++ 公司研发出了一项新的黑科技——传送门，现在他们要在各大城市举行展览会！
Au 国的 $n$ 个城市呈线性排列（城市从 $1$ 到 $n$ 编号），即第 $i$ 个城市到第 $i + 1$ 个城市有一条互相通达的长度为 $1$ 的道路$(i < n)$，现在 Au++ 公司希望将一对（两个）传送门放到一个或两个城市中，供国民观赏。
Au++ 提供了免费试用服务，即来参观的人可以选择进入传送门，瞬间到达另一个传送门所在的城市中去，当然，也可以选择不进入传送门。
现有 $m$ 个人要参加这次展览会，每个人有一个游览计划，可以表示成二元组 $(a, b)$，表示他从城市 $a$ 出发，去参观一次传送门（即要到达一个传送门，但可以选择不进入），然后到城市 $b$ 去。
$m$ 个人都要参加这次展览会，请你帮 Au++ 公司决定把传送门放在哪两个城市，使得所有人走的路的总长度（即忽略参观的时间）最短。
注意：每个人的游览互不影响。
输入格式
第一行两个整数 $n$ 和 $m$。
接下来 $m$ 行，每行两个正整数 $a$ 和 $b$，描述一个人的游览计划。
输出格式
一个正整数，表示最短的总长度。
样例一
input
5 2
1 3
2 4output
2explanation
将传送门分别放在 $2$、$3$ 号城市即可。这样两个人都需要走 $1$ 的长度。
样例二
见样例数据下载
限制与约定
对于 $30\texttt{%}$ 的数据，$n,m \le 100$
对于 $60\texttt{%}$ 的数据，$n,m \le 2000$
对于另外 $20\texttt{%}$ 的数据，对于所有人有 $a = b$
对于 $100\texttt{%}$ 的数据，$3 \le n,m \le 10^6$，对于所有人有 $a,b \le n$
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$
