题目描述

小 Z 变成了国际象棋中的一个“马”骑士，众所周知，马在国际象棋中是走“日”字型路线的，如下图中，马可以跳到红色的八个格子。

小 Z 所在的棋盘有 $n$ 行 $n$ 列，其中有 $k$ 个位置放置了小兵，小兵是无法移动的。小 Z 作为骑士要消灭这 $k$ 个小兵。

小 Z 可以从任意一个小兵的位置出发，通过走“日”字型的条约，达到这 $k$ 个格子至少一次，并最终回到起点。问，小 Z 最少需要走几步。

小兵的坐标用 $(x_i,y_i)$ 表示在棋盘的第 $x_i$ 行第 $y_i$ 列，例如棋盘左上角坐标为 $(1,1)$ 右下角坐标为 $(n,n)$ 。

输入格式

第一行输入两个整数 $n,k$ 分别表示棋盘的大小和小兵的数量。

接下来有 $k$ 行，第 $i$ 行输入 $x_i,y_i$ 表示小兵所在的位置。

一行一个整数表示答案。

$4\le n \le 20,1\le k \le 10$