Training Site
Sideways banner

Flower Garden 2

Input: Standard Input (stdin)
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.


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 i-th activation.


Output a single integer: the number of flowers that the machine watered in at least one of its N activations.


  • 1 ≤ N ≤ 700
  • 0 ≤ A ≤ 500
  • 0 ≤ r_i, c_i ≤ 10^{12}


  • 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.


  • 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.
  • Sample Input 1

    3 1
    0 0
    1 1
    2 2

    Sample Output 1

  • Sample Input 2

    2 2
    1 1
    4 4

    Sample Output 2

  • Sample Input 3

    2 0
    23 45
    12 92

    Sample Output 3