Flower Garden 2

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 $i$th 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 $i$th of the next $N$ lines of input each contain two integers $r_i$ and $c_i$ which is the centre of the $i$-th 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 type-sensitive language such as C, C++, C# or Java, you should use 64-bit integer types to prevent integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.