n,m = map(int,input().split())
NM = [list(map(int,input().split())) for i in range(n*m)]

ans = 10**10

def calc(x,y):

    if x == n-1:
        target = set([1,n,n-1,n-2,n-3])
    else:
        target = set([x-2,x-1,x,x+1,x+2])

    
    num = 0

    turn = -1
    now = 0
    while num < 5:

        turn += 1

        dif = 5-num

        for i in range(dif):
            nx,ny = NM[now]
            now += 1
            if ny == y and nx in target:
                num += 1
        
    return turn
for i in range(3,n):
    for j in range(1,m+1):
        ans = min(ans,calc(i,j))

print(ans)