Cho hình vuông NxN, một số ô có các hộp, mỗi ô có thể có nhiều hộp bao nhau. Tính số hộp cần chuyển ít nhất để các hộp này xếp thành 1 hình chữ nhật (mỗi ô chỉ có 1 hộp). Phép chuyển hộp là chuyển 1 hộp ở trên cùng ở một ô vuông sang và đặt ở trên cùng 1 ô vuông nào khác.

Input

DÒng đầu là 2 số N và M, (1 ≤ N ≤ 100, 1 ≤ M ≤ N^2), kích thước hình vuông và số hộp. M dòng tiếp theo là tọa độ mỗi hộp (hàng, cột).

Output

Số hộp ít nhất cần chuyển

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  
  
Ở ví dụ 2, hộp chuyển từ (2, 3) tới (3, 3), từ (4, 2)  
tới (2, 5) và từ (4, 4) tới (3, 5).