Đồng cỏ lớn nhất của Farmer John có thể được xem là một lưới lớn gồm các ô vuông hai chiều. Hiện có \(N\) con bò đứng trong một số ô của lưới (\(1\le N\le 200\)).

Farmer John muốn dựng một hàng rào bao quanh một vùng ô hình vuông. Các cạnh của hình vuông phải song song với các trục \(x\) và \(y\), và vùng này có thể nhỏ đến mức chỉ gồm một ô. Hãy giúp ông đếm số tập con bò phân biệt có thể được bao trong một vùng như vậy. Lưu ý rằng tập rỗng cũng được tính.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên, cách nhau bởi dấu cách, là tọa độ \((x,y)\) của ô có một con bò. Mọi tọa độ \(x\) đôi một khác nhau và mọi tọa độ \(y\) cũng đôi một khác nhau. Tất cả các giá trị \(x\) và \(y\) nằm trong đoạn \(0\ldots 10^9\).

Mặc dù tọa độ các ô có bò đều không âm, vùng hình vuông được rào có thể kéo dài sang những ô mang tọa độ âm.

Dữ liệu ra

In số tập con bò mà FJ có thể bao bằng hàng rào. Có thể chứng minh rằng giá trị này vừa trong một số nguyên có dấu 32 bit.

Phân nhóm

• Trong các test 1-5, mọi tọa độ của ô có bò đều nhỏ hơn \(20\).
• Trong các test 6-10, \(N\le 20\).
• Trong các test 11-20, không có ràng buộc bổ sung.

Ví dụ

4
0 2
2 3
3 1
1 0

14

16
17 4
16 13
0 15
1 19
7 11
3 17
6 16
18 9
15 6
11 7
10 8
2 1
12 0
5 18
14 5
13 2

420

Nguồn

USACO 2020 December Contest, Gold - Square Pasture: https://usaco.org/index.php?page=viewproblem2&cpid=1067

Tác giả: Benjamin Qi.