Gathering Points

There is a grid with $N$ rows and $N$ columns, and $M$ points are placed on it. Below is an example with $N = 4$ and $M = 4$. The numbers to the left of the grid are row numbers and the numbers above are column numbers; the position of each cell is written as (row, column).

We now want to gather all of the points on the grid into a single cell. A point may move only one cell at a time, to a cell directly above, below, to the left of, or to the right of the cell it currently occupies.

When all points are gathered into one cell, we consider the total distance (the number of cell moves) travelled by the points. For example, if the points above are gathered into cell (3, 2) along shortest paths, the point at (1, 2) moves 2 cells, the points at (3, 1) and (4, 2) each move 1 cell, and the point at (1, 4) moves 4 cells, so the total distance is 8. Gathering the same points into cell (1, 2) also gives a total distance of 8. In this example there is no cell for which the total distance is smaller than 8.

Your task is to find the minimum possible total distance needed to gather all points on the grid into a single cell. A single cell may hold several points at once, and the target cell may be any cell of the grid (including one that already contains a point).

The first line contains the grid size $N$ and the number of points $M$, separated by a single space. Each of the next $M$ lines contains two integers, the row number and the column number of one point, separated by a single space. Here $1 \le N \le 10{,}000$ and $1 \le M \le 100{,}000$, and each point's row and column are between $1$ and $N$ inclusive.

Print the minimum total distance needed to gather all points into a single cell.