점 모으기

행과 열의 크기가 각각 $N$인 격자 공간에 $M$개의 점이 놓여 있다. 아래는 $N = 4$, $M = 4$인 예이다. 격자 왼쪽의 숫자는 행 번호, 위쪽의 숫자는 열 번호를 나타내며, 각 칸의 위치는 (행 번호, 열 번호)로 표시한다.

이제 격자에 있는 모든 점을 하나의 칸으로 모으려고 한다. 한 점은 자신이 있는 칸에서 상하좌우로 인접한 칸으로만 한 칸씩 움직일 수 있다.

모든 점을 어떤 한 칸으로 모을 때, 각 점이 움직인 거리(움직인 칸의 수)의 합을 생각한다. 예를 들어 위의 점들을 (3, 2) 칸으로 최단 경로를 따라 모으면 (1, 2)의 점은 2칸, (3, 1)과 (4, 2)의 점은 각각 1칸, (1, 4)의 점은 4칸을 움직이므로 이동 거리의 합은 8이다. 같은 점들을 (1, 2) 칸으로 모아도 이동 거리의 합은 8이다. 이 예에서 이동 거리의 합이 8보다 작아지는 칸은 존재하지 않는다.

이 문제는 격자에 있는 모든 점을 하나의 칸으로 모을 때 필요한 이동 거리 합의 최솟값을 구하는 것이다. 한 칸에는 여러 개의 점이 함께 있을 수 있으며, 점들을 모으는 목표 칸은 격자의 어떤 칸이라도 될 수 있다(이미 점이 놓여 있는 칸이어도 된다).

첫 줄에 격자의 크기 $N$과 점의 개수 $M$이 공백을 사이에 두고 주어진다. 이어지는 $M$개의 줄에는 각 줄마다 한 점의 위치를 나타내는 두 정수, 즉 행 번호와 열 번호가 공백을 사이에 두고 주어진다. $N$은 $1 \le N \le 10{,}000$, $M$은 $1 \le M \le 100{,}000$이며, 각 점의 행 번호와 열 번호는 $1$ 이상 $N$ 이하이다.

모든 점을 하나의 칸으로 모을 때 필요한 이동 거리 합의 최솟값을 한 줄에 출력한다.