시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

Farmer John's largest pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Currently, there are $N$ cows occupying some of these cells ($1 \leq N \leq 200$).

Farmer John wants to build a fence that will enclose a square region of cells; the square must be oriented so its sides are parallel with the $x$ and $y$ axes, and it could be as small as a single cell. Please help him count the number of distinct subsets of cows that he can enclose in such a region. Note that the empty subset should be counted as one of these.

## 입력

The first line contains a single integer $N$. Each of the next $N$ lines Each of the next $N$ lines contains two space-separated integers, indicating the $(x,y)$ coordinates of a cow's cell. All $x$ coordinates are distinct from each-other, and all $y$ coordinates are distinct from each-other. All $x$ and $y$ values lie in the range $0 \ldots 10^9$.

Note that although the coordinates of cells with cows are nonnegative, the square fenced area might possibly extend into cells with negative coordinates.

## 출력

The number of subsets of cows that FJ can fence off. It can be shown that this quantity fits within a signed 32-bit integer.

## 예제 입력 1

4
0 2
2 3
3 1
1 0


## 예제 출력 1

14


In this example, there are $2^4$ subsets in total. FJ cannot create a fence enclosing only cows 1 and 3, or only cows 2 and 4, so the answer is $2^4-2=16-2=14$.

## 예제 입력 2

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


## 예제 출력 2

420