Grand master - danh hiệu thể hiện vị trí cao thủ trong một lĩnh vực nào đó. Trong cờ tướng, người ta gọi đó là "quốc tế đại sư". Ở CLB H3.2, có đại sư Đức Tài ngày đêm luyện tập chuyên tâm để tranh hùng với các đối thủ nặng ký khác. Một ngày nọ, trong giấc mơ, Tài gặp một bàn cờ khổng lồ kích thước ~n \times n~ và trên đó có một số ô có chướng ngại vật. Một đối thủ là anh N. giấu tên yêu cầu Tài phải đặt được 2 quân mã vào 2 ô nào đó của bàn (tránh các chướng ngại vật) sao cho 2 quân không ăn nhau. Hỏi đại sư của H3.2 có mấy cách đặt cặp quân mã như vậy đây?

Ghi chú: quân mã ở vị trí ~(a,b)~ có thể tấn công được ô ~(c,d)~ nếu như ~\mid (a-c)(b-d) \mid=2~, nghĩa là chênh lệch theo hàng và theo cột là ~1,2~ hoặc ~2,1.~

Input

Dòng đầu tiên gồm số nguyên ~n,m~ với ~n~ là kích thước bảng ~1 \le n \le 2025~ và ~m~ là các chướng ngại vật với ~0 \le m \le 25.~ Mỗi dòng tiếp theo trong ~m~ dòng là cặp số ~x,y~ cho biết tọa độ của ô chướng ngại vật (giả sử bàn cờ được đánh số chiều ngang - dọc từ ~1~ đến ~n~), trong đó ~1 \le x,y \le n~ và các cặp tọa độ sẽ không bị lặp lại.

Output

Đáp số của bài toán.

Sample input 1

3 0

Sample output 1

28

Sample input 1

4 2
1 3
3 4

Sample output 1

72

Giải thích

Trong VD1 đã cho, ta thấy có ~3 \times 3 = 9~ ô nên để chọn ra hai ô, ta có ~C_9^2 = 36~ cách. Tuy nhiên, ta đếm được ~8~ cặp ô mà các quân mã tấn công được nhau nên có ~36-8=28~ cách.