MNERED  NERED
English  Vietnamese 
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.
Input
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
Output the smallest number of moves. A solution will always exist.
Sample
input
4 3
2 2
4 4
1 1
output
2
input
5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3
output
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:
20180819 04:54:42
Super naive algo passed :'( 

conquistador:
20180303 20:34:22
just check if it possible in every sub rectangle of possible to arrange the boxes 

xodiac:
20171114 20:43:31
Nice question


sujoy_3:
20170929 12:29:44
Can someone elaborate the question? Last edit: 20170929 12:30:14 

hodobox:
20160830 05:41:33
O(N^3) still chill. 

farhad chowdhury:
20160422 02:22:20
century


Utkarsh Saxena:
20140903 22:50:54
O(n^2 * sqrt(m)) :D 

shashank:
20140129 21:38:30
Nice question ..


Martijn Muijsers:
20131201 14:20:30
My incredibly naive algorithm gets TLE :( boohoo :P 

hamza007:
20120620 14:46:33
interesting !! Brute force gets accepted in 0.07 .. 
Added by:  ~!(*(@*!@^& 
Date:  20090308 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COCI 6th 09 