Problem Description

Given $ N $ points $(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$ on a 2D plane and a non-negative integer $ D $.

Find the number of pairs of integers $ (x,y) $ that satisfy $\displaystyle\ \sum_{i=1}^N\ (|x-x_i|+|y-y_i|)\ \leq\ D$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ D $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $\vdots$ $ x_N $ $ y_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 3
0 0
1 0

Sample Output #1

8

Sample Input #2

2 0
0 0
2 0

Sample Output #2

0

Sample Input #3

6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

Sample Output #3

419

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ D\ \leq\ 10^6$
• $-10^6\ \leq\ x_i,\ y_i\ \leq\ 10^6$
• $(x_i,y_i)\ \neq\ (x_j,y_j)$ for $i\neq\ j$
• All inputs are integers

Sample Explanation 1

The figure below visualizes the input and answer for Sample 1. The blue dots represent the input points. A total of 8 points, including the blue and red dots, satisfy the condition in the problem statement. 

见题面 Input 部分

见题面 Output 部分