题目描述

有一个$n\times n$的围棋棋盘，初始时棋盘中一个棋子都没有。你可以进行$m$次操作，每次选择一个位置$(x,y)$放置黑色棋子，请问你至少需要几次操作才能在棋盘中摆出一个$3\times 3$的矩阵全是黑色棋子。如果无解输出no。

输入格式

第一行两个正整数n和m，分别表示$n\times n$的棋盘和$m$次操作。

接下来$m$行，每行两个整数$x$和$y$，表示在$(x,y)$上放置黑色棋子。

输出格式

一个正整数，表示至少需要几次操作可以摆出3*3的全是黑色棋子。

输入数据 1

4 11
1 1
1 2
1 3
2 2
2 3
1 4
2 4
3 4
3 2
3 3
4 1

输出数据 1

10

数据范围

$1 \le n \le 1000,1 \le m \le min(n*n,10^5),1\le x,y \le n$