BÀI TEST TÍNH NĂNG TRẮC NGHIỆM (QUIZ)

Đây là bài kiểm tra thử nghiệm tính năng trắc nghiệm mới trên hệ thống UMTOJ.

Thông tin bài tập:

• Số lượng câu: 30 câu.
• Nội dung: Toán rời rạc, Cấu trúc dữ liệu, Tin học đại cương.
• Lưu ý quan trọng: Hệ thống đã kích hoạt chế độ One-shot (Nộp 1 lần). Bạn sẽ không thể sửa lại bài sau khi đã bấm nộp.

Yêu cầu:

1. Làm đủ các câu hỏi.
2. Test thử khả năng hiển thị công thức Toán học.
3. Bấm nộp bài và xem kết quả chấm tự động.

Đón chào mùa hè 2025, tạm biệt mùa thi, các sinh viên và giảng viên UMT cùng nhau chơi một trò chơi điện tử liên quan đến linh vật của năm để xã stress, đó chính là trò chơi con rắn. Trên bản đồ thần kỳ kích thước ~n × n~ (với ~1 ≤ n ≤ 10^9~), có sẵn ~m~ hạt đậu may mắn được cất giữ tại các vị trí có tọa độ nguyên (~x_1~, ~y_1~),(~x_2~, ~y_2~), . . . ,(~x_m~, ~y_m~) với ~1 ≤ m ≤ 2025~. Mỗi hạt đậu được cho là mang theo những lời chúc phúc cho năm mới. Người chơi sẽ điều khiển con rắn ăn hết các hạt đậu trong thời gian càng nhanh càng tốt. Từ một vị trí có toạ độ nguyên (x, y), con rắn có thể đi đến một trong các vị trí kề với nó là ~(x - 1, y)~,~(x, y - 1)~,~(x + 1, y)~,~(x, y + 1)~ tốn thời gian 1 giây.

Là người mở màn cho trò chơi này, thầy Hồng khởi đầu hành trình từ ô ~(x_1, y_1)~ (vừa là vị trí của hạt đậu đầu tiên) và chiến lược chơi của thầy như sau: thầy điều khiển con rắn di chuyển tới vị trí chứa hạt đậu gần nhất mà nó chưa ăn qua. Thầy nhận thấy rằng để đi được từ vị trí ~(x, y)~ đến vị trí ~(x', y')~ thì con rắn sẽ tốn thời gian ít nhất là ~|x - x'|+|y - y'|~, chính là khoảng cách Manhattan và vị trí gần nhất ở trên được xét theo khoảng cách này. Nếu có nhiều đậu cùng khoảng cách tối thiểu thì ưu tiên chọn đậu có hoành độ nhỏ nhất, còn nếu tiếp tục có nhiều đậu có cùng hoành độ nhỏ nhất thì chọn đậu có số thứ tự nhỏ nhất theo danh sách được cung cấp. Cứ như vậy, thầy điều khiển con rắn bò tới từng ô và ăn hạt đậu cho đến khi không còn đậu chưa bị thưởng thức.

Tất nhiên cách chơi của thầy chưa phải là chiến lược tối ưu về mặt thời gian để ăn được hết các hạt đậu, nhưng bạn thử giúp thầy Hồng tính xem tổng thời gian cần thiết để thầy thực hiện là bao nhiêu nhé.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ với ~1 ≤ n ≤ 10^9~ và ~1 ≤ m ≤ min{2025, n×n}~. ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~ ~(1 ≤ x_i, y_i ≤ n)~ - tọa độ của hạt đậu thứ ~i~ trên bảng, biết rằng sẽ không có ô nào trùng nhau.

Output

Một số nguyên duy nhất là tổng thời gian mà thầy Hồng điều khiển con rắn đã bò theo toàn bộ hành trình.

Sample Input 1

3 2
1 1
2 3

Sample Ouput 1

3

Sample Input 2

10 4
1 6
5 6
4 7
4 5

Sample Ouput 2

8

Giải thích

Trong Ví dụ thứ 1, thầy Hồng sẽ cho con rắn di chuyển từ ~(1, 1)~ đến ~(2, 3)~ thông qua các ô như sau: ~(1, 1) → (1, 2) → (1, 3) → (2, 3)~ với tổng thời gian là 4. Khoảng cách này cũng được tính nhanh chóng nhờ công thức ~|2 - 1| + |3 - 1| = 3~. Trong Ví dụ 2, từ ~(1, 6)~, ta thấy khoảng cách đến các điểm còn lại đều là 4 vì ~|4 - 1| + |7 - 6| = |5 - 1| + |6 - 6| = |4 - 1| + |5 - 6| = 4~. Khi đó, thầy Hồng sẽ ưu tiên chọn hoành độ nhỏ nhất, nhưng có hai điểm như vậy là ~(4, 7)~ và ~(4, 5)~, mà điểm ~(4, 7)~ nằm trước trong danh sách nên thầy sẽ ưu tiên chọn điểm đó để đi. Sau đó, thầy đi qua ~(4, 5)~ và ~(5, 6)~. Tổng thời gian là ~4 + 2 + 2 = 8~.

Subtask:

• Subtask 1 (25% số điểm): ~n ≤ 10~.

• Subtask 2 (75% số điểm): Không giới hạn gì thêm.

Ở mùa giải ICPC 2025 mới, nhân lực của CLB lập trình của UMT rất đông và hung hãn. Năm nay kỳ thi ICPC cấp khu vực sẽ tổ chức tại TP.HCM nên không có lý do gì mà UMT không huy động nhân lực để tham gia được nhiều team càng nhiều càng tốt.

Trong CLB hiện tại có tất cả ~n~ thành viên và sau quá trình dài tham gia thi trên codeforces.com cũng như nhiều nên tảng khác thì thầy Trung chủ nhiệm CLB đánh giá rằng mỗi người có một điểm số năng lực nhất định (tất nhiên có thể có nhiều người có cùng điểm số năng lực). Thầy Trung muốn các bạn tạo với nhau thành các team ba người, trong đó hai thành viên bất kỳ cùng team thì chênh lệch điểm số năng lực không quá 2 đơn vị. Hãy giúp thầy Trung đếm xem có tất cả bao nhiêu cách khác nhau để tạo team theo ràng buộc trên nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 ≤ n ≤ 10^5~.

Dòng tiếp theo gồm điểm số năng lực của các thành viên, có giá trị nguyên dương không vượt quá ~10^9~

Output

Số team có thể tạo thành.

Sample Input 1

4
11 12 13 14

Sample Ouput 1

2

Sample Input 2

5
1 1 1 1 1

Sample Ouput 2

10

Giải thích

Trong Ví dụ 1, ta thấy các bạn có số thứ tự (1, 2, 3) và (2, 3, 4) có thể cùng team với nhau; còn trong Ví dụ 2, ta thấy ba bạn bất kỳ đều có thể tạo thành team, số cách chọn là ~C_{5}^{3}=10~.

Subtask:

• Subtask 1 (50% số điểm): ~n ≤ 10~.

• Subtask 2 (50% số điểm): Không giới hạn gì thêm.