题目描述

我们知道在国际象棋中，皇后每次可以在垂直方向或者水平方向移动任意距离，所以皇后可以攻击和它处于同一行或者同一列的棋子。

现在有一个 $m * m$ 的棋盘，行列编号分别为 $1,2,3...m$，在这个棋盘中已经摆好了 $n$ 个皇后，而且保证它们无法互相攻击。

但是 gsy 是个完美主义者，她觉得这 $n$ 个皇后散落在整个棋盘中太不规则了，她希望可以经过移动将这些皇后移动到主对角线上。

gsy 每次能够按照国际象棋的规则选择一个皇后进行一次移动，但是要注意，这次移动以后的棋盘依旧要保持和平，不能出现皇后能攻击皇后的情况。

现在告诉你这 $n$ 个皇后所在的坐标，请你告诉 gsy，她最少需要几次移动才可以使得这 $n$ 个皇后都在主对角线上？

P.S. 主对角线即 $(1,1),(2,2),(3,3)...(m,m)$

输入格式

第一行包含两个正整数 $m, n$ 含义如题所示。 接下来 $n$ 行，每行包含两个正整数 $x_i,y_i$ 表示一个皇后的坐标

输出格式

输出最少需要移动的次数。

数据范围

对于 $30\%$ 的数据，$2 \leq m \leq 20$

对于 $100\%$ 的数据，$2 \leq m \leq 10^5 , x_i,y_i \leq m$

对于所有数据保证 $n < m$

5 2
3 4
4 3

3

样例解释

对于样例，需要经过以下三步:

1. $(3,4) \rightarrow (3,5)$
2. $(4,3) \rightarrow (4,4)$
3. $(3,5) \rightarrow (3,3)$