Giải bài trực tuyến

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).