Flower Garden 2
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 2.0 seconds
You have a garden made up of flowers arranged in a grid. There is an infinite number of rows stretching South, numbered 0, 1, 2... and so on. There is also an infinite number of columns stretching East, numbered 0, 1, 2... and so on. You have set upon yourself the impossible task of watering all of the flowers, and as such, you have acquired a machine to help you do that.
Unfortunately the machine has gone haywire, and activated N times outside of your control. On the ith activation, it watered all of the flowers within an (A × 2 + 1) by (A × 2 + 1) square region centred at the flower in row r_i and column c_i. Notice that this could potentially hang off of the North and West edges of the garden. In that case, only the flowers within the garden were watered. Now that you've finally managed to disable the machine, you want to work out how many flowers have been watered at least once.
Input
The first line of input contains two integers N, and A.
The ith of the next N lines of input each contain two integers r_i and c_i which is the centre of the ith activation.
Output
Output a single integer: the number of flowers that the machine watered in at least one of its N activations.
Constraints
 1 ≤ N ≤ 700
 0 ≤ A ≤ 500
 0 ≤ r_i, c_i ≤ 10^{12}
Subtasks
 Subtask 1 (10%): N = 2
 Subtask 2 (25%): r_i, c_i ≤ 1,000 and A ≤ 50
 Subtask 3 (25%): For all values of i, it holds that (r_i = c_i).
 Subtask 4 (40%): No further constraints.
Sample 1 Explanation
The first sample case is illustrated below. The blue squares each represent a machine activation. We can see that a total of 14 flowers within the garden were watered.
Note
 If you are using Python, select
Python 3.6 (PyPy 7.3)
when submitting. Otherwise, your solution may not pass the time limit even if it is maximally efficient.  If you're using a typesensitive language such as C, C++, C# or Java, you should use 64bit integer types to prevent integer overflow. 64bit integer types include
long
long
for C or C++, andlong
for C# or Java.

Sample Input 1
3 1 0 0 1 1 2 2
Sample Output 1
14

Sample Input 2
2 2 1 1 4 4
Sample Output 2
37

Sample Input 3
2 0 23 45 12 92
Sample Output 3
2