事件解決の鍵は犯行開始時刻です。以下、\(T_i\) の最大値（犯行開始には遅すぎる時刻）を \(M\) とします。

犯行開始時刻が \(t\) であるときに犯人のペアとしてありうるものの個数を \(p_t\) とします。犯行開始時刻は \(1\) 以上 \(M\) 以下の整数であり、犯行開始時刻が違えば異なるシナリオとして数えられるため、答えは \(p_1 + p_2 + \dots + p_M\) です。

犯行開始時刻が \(t\) であるときに犯行開始から犯行終了まで常に館にいる人数を \(c_t\) とします。\(c_t\) 人のうちどの \(2\) 人を選んでもありうるシナリオが得られるため、\(p_t = {}_{c_t} \mathrm{C}_2 = \frac{c_t \times (c_t - 1)}{2}\) です。

\(c_t\) は時刻 \(t\) から時刻 \(t + D\) まで常に館にいる人の数です。すなわち、\(S_i \leq t\) かつ \(t + D \leq T_i\) を満たす人 \(i\) の数です。\(t + D \leq T_i\) を \(t \leq T_i - D\) と書き換えると、人 \(i\) の退館時刻を \(T_i - D\) に変えたときに時刻 \(t\) に館にいる人数と解釈できます（もともと滞在時間が \(D\) 未満の人は無視します）。この解釈のもとで人の出入りをシミュレートすることで \(c_1, \dots, c_M\) がすべて求まり、それを使って答えを計算できます。時間計算量は \(O(N + M)\) です。

Python での実装例

N, D = map(int, input().split())
M = 10**6 + 1
d = [0] * M
for i in range(N):
    S, T = map(int, input().split())
    if T - S >= D:
        d[S] += 1
        d[T - D + 1] -= 1

c, ans = 0, 0
for i in range(M):
    c += d[i]
    ans += c * (c - 1) // 2
print(ans)