Rectangular One Formation

Given an n x n matrix where every cell initially contains 0, you are given m modifications. Each modification increases the value at a specified cell by 1. After all modifications, the matrix has a total sum of m, but some cells may have values greater than 1.

You can perform the following operation: choose any cell with a nonzero value and decrease its value by 1, then choose any cell (possibly with 0) and increase its value by 1. Each such operation counts as a single step.

The goal is to reach a configuration where every cell is either 0 or 1, and all cells with value 1 form a contiguous rectangle. Note that the area of this rectangle must be exactly m. Equivalently, if the rectangle dimensions are \(r\) and \(c\) then \(r\times c=m\) with \(r,c\le n\). It is guaranteed that such a rectangle exists.

Determine the minimum number of operations needed.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(1 \le n \le 10^3\) and \(0 \le m \le n^2\). Each of the next \(m\) lines contains two integers \(i\) and \(j\) (1-indexed) indicating that the cell at row \(i\) and column \(j\) is increased by 1.

outputFormat

Output a single integer representing the minimum number of operations required to achieve the desired configuration.

sample

3 2
1 1
2 2

0