P6032 Choose Inns (Enhanced Version).

There are $n$ distinctive inns along the Lijiang River, numbered from $1$ to $n$ in order of their locations. Each inn is decorated in one of $k$ color tones (represented by integers $0 \sim k-1$). Each inn also has a coffee shop, and each coffee shop has its own minimum spending requirement. Two tourists travel to Lijiang together. They like the same color tone and want to try two different inns, so they decide to stay in two inns that have the same tone. In the evening, they plan to choose a coffee shop to have coffee. The coffee shop must be located between the two inns they stay in (including those two inns), and its minimum spending requirement must not exceed $p$. They want to know how many different ways to choose the two inns to stay in, such that they are guaranteed to find at least one coffee shop with minimum spending not exceeding $p$ for their evening meetup.

The input has $n+1$ lines. The first line contains three integers $n, k, p$, separated by a single space, representing the number of inns, the number of tones, and the maximum acceptable minimum spending. The next $n$ lines: the $(i+1)$-th line contains two integers separated by a single space, representing the decoration tone of inn $i$ and the minimum spending of the coffee shop at inn $i$.

Output one line containing one integer, representing the total number of valid ways to choose the inns to stay in.

[Sample Explanation] $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textsf{客栈编号} & \text{①} & \text{②} & \text{③} & \text{④} & \text{⑤} \\\hline \textsf{色调} & 0 & 1 & 0 & 1 & 1 \\\hline \textsf{最低消费} & 5 & 3 & 2 & 4 & 5 \\ \hline \end{array}$$ The two people must stay in inns with the same tone. All possible choices of inns include: staying in inns ① and ③, ② and ④, ② and ⑤, ④ and ⑤. However, if they choose inns ④ and ⑤, then among the coffee shops between inns ④ and ⑤, the minimum spending is $4$, while the maximum minimum spending they can accept is $3$, so it does not meet the requirement. Therefore, only the first $3$ choices are valid. [Constraints] For $25\%$ of the testdata, $n \leq 100$. For $40\%$ of the testdata, $n \leq 1000$. For $80\%$ of the testdata, $n \leq 2 \times 10^5$, $k \leq 50$. For $100\%$ of the testdata, $2 \leq n \leq 2 \times 10^6$, $1 \leq k \leq 10^4$, $0 \leq p \leq 100$, $0 \leq$ minimum spending $\leq 100$. Translated by ChatGPT 5