An important fact is that, if an integer pair \((l,r)\) satisfies the conditions, then so does \((l+1,r)\). Thus, there exists \(d_r\) such that:

• For a fixed \(r\), a pair \((l,r)\) satisfies the conditions if and only if \(l\) is an integer between \(d_r\) and \(r\), inclusive.

If one can find this \(d_r\) for each \(r\), the sought answer can be found as \(\displaystyle \sum_{r=1}^M \left(r-d_r+1 \right)\). We will now consider how to find this \(d_r\).

Suppose that we already know \(d_{r-1}\) and now want to find \(d_r\). If there is no \(i\) with \(R_i=r\), then there are no new constraints, so \(d_r=d_{r-1}\). If there exists such \(i\), we have \(d_r=\max(d_{r-1},L_{\max}+1)\), where \(L_{\max}\) is the maximum \(L_i\) for \(i\) with \(R_i=r\).

By incrementally evaluating these recurrence relations, we can find all \(d_r\) starting from \(d_1\) in order.

The problem can be solved by appropriately implementing this procedure. The complexity is \(O(N+M)\).

Sample code (Python3)

N, M = map(int, input().split())
d = [1 for i in range(M + 1)]
for _ in range(N):
    L, R = map(int, input().split())
    d[R] = max(d[R], L + 1)
for r in range(1, M + 1):
    d[r] = max(d[r], d[r - 1])
ans = 0
for r in range(1, M + 1):
    ans += r - d[r] + 1
print(ans)