In the nearby kindergarten they recently made up an attractive game of strength and agility that kids love.

The surface for the game is a large flat area divided into \(N \times N\) squares.

The children lay large spongy cubes onto the surface. The sides of the cubes are the same length as the sides of the squares. When a cube is put on the surface, its sides are aligned with some square. A cube may be put on another cube too.

Kids enjoy building forts and hiding them, but they always leave behind a huge mess. Because of this, prior to closing the kindergarten, the teachers rearrange all the cubes so that they occupy a rectangle on the surface, with exactly one cube on every square in the rectangle.

In one move, a cube is taken off the top of a square to the top of any other square.

Write a program that, given the state of the surface, calculates the smallest number of moves needed to arrange all cubes into a rectangle.

The first line contains the integers \(N\) and \(M\) (\(1 \le N \le 100\), \(1 \le M \le N^2\)), the dimensions of the surface and the number of cubes currently on the surface.

Each of the following \(M\) lines contains two integers \(R\) and \(C\) (\(1 \le R, C \le N\)), the coordinates of the square that contains the cube.

Output the smallest number of moves. A solution will always exist.

riseoj 작성

출처 COCI 2008/2009 Contest 6