The key to solving the case is the time the crime began. Let \(M\) be the maximum value of \(T_i\) (a time that is too late to start the crime).

Let \(p_t\) be the number of possible pairs of culprits that can start a crime at time \(t\). The crime start at an integer time between \(1\) and \(M\), and different starting times are counted as different scenarios, so the answer is \(p_1 + p_2 + \dots + p_M\).

Let \(c_t\) be the number of candidates staying in the house throughout the crime if the crime began at time \(t\). Any choice of two candidates yield different scenarios, so the answer is \(p_t = {}_{c_t} \mathrm{C}_2 = \frac{c_t \times (c_t - 1)}{2}\).

\(c_t\) is the number of candidates that were ins the house from time \(t\) to time \(t+D\), that is, the number of \(i\) such that \(S_i \leq t\) and \(t + D \leq T_i\). By replacing \(t + D \leq T_i\) with \(t \leq T_i - D\), it ca be interpreted as the number of people who were in the house at time \(t\) when person \(i\)’s leaving time is changed to \(T_i - D\) (ignoring those who stayed in the house less than duration \(D\)). By simulating who enters and leaves the house as the time evolves, we can find all \(c_1, \dots, c_M\), allowing us to find the answer. The time complexity is \(O(N + M)\).

Sample code in 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)