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×N squares. The children lay large spongy cues 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 moving, 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 ≤ N ≤ 100, 1 ≤ M ≤ 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 ≤ R, C ≤ N), the coordinates of the square that contains the cube.




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



4 3
2 2
4 4
1 1

5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3

In the second example, a cube is moved from (2, 3) to (3, 3), from (4, 2)
to (2, 5) and from (4, 4) to (3, 5).

hide comments
ttnhuy313: 2018-08-19 04:54:42

Super naive algo passed :'(

conquistador: 2018-03-03 20:34:22

just check if it possible in every sub rectangle of possible to arrange the boxes

xodiac: 2017-11-14 20:43:31

Nice question
just think about factors of m

sujoy_3: 2017-09-29 12:29:44

Can someone elaborate the question?

Last edit: 2017-09-29 12:30:14
hodobox: 2016-08-30 05:41:33

O(N^3) still chill.

farhad chowdhury: 2016-04-22 02:22:20

made it with 0.0 time

Utkarsh Saxena: 2014-09-03 22:50:54

O(n^2 * sqrt(m)) :D

shashank: 2014-01-29 21:38:30

Nice question ..
Shocked when got AC in first attempt..

Martijn Muijsers: 2013-12-01 14:20:30

My incredibly naive algorithm gets TLE :( boohoo :P

hamza007: 2012-06-20 14:46:33

interesting !! Brute force gets accepted in 0.07 ..

Added by:~!(*(@*!@^&
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COCI 6th 09