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 = [1,n,n-1,n-2,n-3]
    else:
        target = [x-2,x-1,x,x+1,x+2]

    
    num = 0

    for i in range(5):
        nx,ny = NM[i]
        if ny == y and nx in target:
            num += 1

    turn = 0
    now = 5
    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)