本問題は尺取り法の練習問題です．以下の解説では，尺取り法を知っていることを前提とします．

\(f(x) = \displaystyle \sum_{i=1}^N |x-x_i|,\,g(y) = \displaystyle \sum_{i=1}^N |y-y_i|\) と定義します．すると，答えは \(f(x) + g(y) \leq D\) を満たす \((x,y)\) の個数になります．

座標の絶対値の最大値を \(M\) とします． \(|x| > M + D\) または \(|y| > M + D\) のとき， \(f(x),g(y)>D\) なので， \(|x|,|y| \leq M + D\) を満たす \((x,y)\) のみ考えればよいです．

答えを求めるには，以下の2つの問題が高速に解ければよいです．

1. \(|x|,|y| \leq M+D\) を満たす \(x,y\) に対して \(f(x),g(y)\) を求める
2. \(|x| \leq M+D\) を満たす \(x\) に対して， \(f(x)+g(y) \leq D\) を満たす \(y\) の個数を求め，その総和を求める

順に説明します．

問題1の解法

\(f(x)\) を求める方法を説明します．\((x_1,x_2,\dots,x_N)\) をソートしておき，\(x_1\leq x_2 \leq \dots \leq x_N\) とします．

まず， \(x=-(M+D)\) に対し，\(f(x)\) を愚直に求めます． 次に，\(f(x-1)\) が求められているときに \(f(x)\) を求めます．差分を考えると，\(f(x)\) は「\(f(x-1)\) \(+\) (\(x_i< x\) を満たす \(i\) の個数) \(-\) (\(x_i \geq x\) を満たす \(i\) の個数) 」と表されます．(\(x_i < x\) を満たす \(i\) の個数) は \(x\) について単調増加であるため，尺取り法を用いて高速に求めることができます．

問題2の解法

2つの長さ \(2(M+D)+1\) の数列 \(F=(f(-(M+D)), f(-(M+D)+1),\dots, f(M+D))\) と \(G=(g(-(M+D)), g(-(M+D)+1),\dots, g(M+D))\) を用意します．また，これらを昇順にソートします．

\(i=2(M+D)+1,2(M+D),\dots,1\) の順に， \(F_i + G_j \leq D\) を満たす \(j\) の個数を求めます．\(D-F_i\) は単調増加であるため，不等式を満たす \(j\) の個数も単調増加であり，尺取り法を用いて高速に求めることができます．

問題1, 2ともにソートがボトルネックとなり，時間計算量は \(O(N \log N + (M+D) \log (M+D))\) です．

実装例 (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)