Submit solution


Points: 0.36 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
COCI 6th 09
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho hình vuông ~N \times N~, 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 \leq N \leq 100~, ~1 \leq M \leq 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 1

4 3
2 2
4 4
1 1

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

Note

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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.