Chips

Cho một bảng ô vuông kích thước $n\times n$. Trong bảng có $m$ ô bị cấm, các ô còn lại trống. Người chơi lần lượt đặt một số quân cờ (chip) lên các ô nằm ở biên bảng nhưng không phải góc, sao cho mỗi ô biên chứa nhiều nhất một quân.

Sau khi đặt xong, trong đúng $n-1$ phút, mọi quân đều di chuyển đồng thời, mỗi phút đúng một ô, đi thẳng từ cạnh mà nó xuất phát tới cạnh đối diện. Cụ thể:

• Quân đặt ở cạnh trên $(1,j)$ đi xuống dưới: sau phút $t$ đứng ở $(1+t,j)$.
• Quân đặt ở cạnh dưới $(n,j)$ đi lên trên: sau phút $t$ đứng ở $(n-t,j)$.
• Quân đặt ở cạnh trái $(i,1)$ đi sang phải: sau phút $t$ đứng ở $(i,1+t)$.
• Quân đặt ở cạnh phải $(i,n)$ đi sang trái: sau phút $t$ đứng ở $(i,n-t)$.

Người chơi thua (và được $0$ điểm) nếu xảy ra ít nhất một trong các tình huống sau tại một thời điểm bất kỳ trong $n-1$ phút:

1. Có một quân rơi vào ô cấm.
2. Có hai quân đứng trên cùng một ô.
3. Có hai quân hoán đổi vị trí trong cùng một phút (ví dụ đặt hai quân ở hai đầu đối diện của một hàng có độ dài chẵn: chúng sẽ đổi chỗ ở giữa hàng).

Nếu không xảy ra tình huống nào ở trên, người chơi thắng và nhận điểm bằng số quân đã đặt. Hãy tính số điểm lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ — tọa độ hàng và cột của ô cấm thứ $i$. Các ô cấm đôi một khác nhau.

Hàng được đánh số từ $1$ (trên cùng) đến $n$ (dưới cùng); cột được đánh số từ $1$ (trái) đến $n$ (phải).

Dữ liệu ra

Một số nguyên duy nhất — số điểm lớn nhất mà người chơi có thể đạt được.

Ràng buộc

• $2\le n\le 1000$
• $0\le m\le {10}^5$
• $1\le x_i,y_i\le n$

Ví dụ