This problem is an exercise of sliding window. In this editorial, we assume the knowledge of the sliding window.

Let \(f(x) = \displaystyle \sum_{i=1}^N |x-x_i|\) and \(g(y) = \displaystyle \sum_{i=1}^N |y-y_i|\); then the answer is the number of pairs \((x,y)\) such that \(f(x) + g(y) \leq D\).

Let \(M\) be the maximum coordinate. If \(|x| > M + D\) or \(|y| > M + D\), then \(f(x),g(y)>D\), so it is sufficient to consider \((x,y)\) with \(|x|,|y| \leq M + D\).

To find the answer, it is sufficient to solve the following two problems:

1. Find \(f(x)\) and \(g(y)\) for given \(x\) and \(y\) with \(|x|,|y| \leq M+D\).
2. Count integers \(y\) satisfying \(f(x)+g(y) \leq D\) for given \(x\) with \(|x| \leq M+D\).

We explain them step by step.

Solution to problem 1

We explain how to evaluate \(f(x)\). Sort \((x_1,x_2,\dots,x_N)\) to make \(x_1\leq x_2 \leq \dots \leq x_N\).

First, for \(x=-(M+D)\), compute \(f(x)\) naively. Then, we find \(f(x)\) based on \(f(x-1)\). Considering the difference, \(f(x)\) equals \(f(x-1)\) + (the number of \(i\) with \(x_i < x\)) + (the number of \(i\) with \(x_i \geq x\)). Since the number of \(i\) with \(x_i < x\) is monotonically increasing with respect to \(x\), it can be found using sliding window fast.

Solution to problem 2

Prepare two sequences \(F=(f(-(M+D)), f(-(M+D)+1),\dots, f(M+D))\) and \(G=(g(-(M+D)), g(-(M+D)+1),\dots, g(M+D))\), each of length \(2(M+D)+1\). Sort them in ascending order.

For \(i=2(M+D)+1,2(M+D),\dots,1\) in order, find the number of \(j\) such that \(F_i + G_j \leq D\). Since \(D-F_i\) is monotonically increasing, so is the number of \(j\) that satisfies the inequality, which can be counted using the sliding window technique.

The time complexity is \(O(N \log N + (M+D) \log (M+D))\), with sorting being bottleneck in both problem 1 and 2.

Sample code (Python)

N, D = map(int, input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
M = 2 * 10**6


def calc(xs):
    xsum = [0] * (2 * M + 1)
    xs.sort()
    i = 0
    xsum[-M] = sum(xs) + N * M
    for x in range(-M + 1, M + 1):
        while i < N and xs[i] < x:
            i += 1
        xsum[x] = xsum[x - 1] + 2 * i - N
    return xsum


xsum = calc(x)
ysum = calc(y)
xsum.sort()
ysum.sort()
ans = 0
j = 0
for i in range(2 * M + 1)[::-1]:
    while j < 2 * M + 1 and xsum[i] + ysum[j] <= D:
        j += 1
    ans += j
print(ans)