P7987 [USACO21DEC] Paired Up G

There are a total of $N$ ($1\le N\le 10^5$) cows on a number line. The position of the $i$-th cow is $x_i$ ($0 \leq x_i \leq 10^9$), and the weight of the $i$-th cow is $y_i$ ($1 \leq y_i \leq 10^4$). According to Farmer John’s signal, some cows will form pairs such that: - Each pair contains two different cows $a$ and $b$ whose positions differ by at most $K$ ($1\le K\le 10^9$); that is, $|x_a-x_b|\le K$. - Each cow is either included in exactly one pair or does not belong to any pair. - **The pairing is maximal**; that is, no two unpaired cows can form a pair. You need to find the possible range of the total weight of unpaired cows. Specifically: - If $T=1$, compute the minimum possible total weight of unpaired cows. - If $T=2$, compute the maximum possible total weight of unpaired cows.

The first line contains $T$, $N$, and $K$. The following $N$ lines each contain $x_i$ and $y_i$. The input guarantees that $0\le x_1< x_2

Output the minimum or maximum possible total weight of unpaired cows.

**Sample Explanation 1** In this example, cows $2$ and $4$ can be paired because their distance is $2$, which does not exceed $K = 2$. This pairing is maximal because the distance between cows $1$ and $3$ is $3$, the distance between cows $3$ and $5$ is $3$, and the distance between cows $1$ and $5$ is $6$, all greater than $K = 2$. The total weight of unpaired cows is $2 + 2 + 2 = 6$. **Sample Explanation 2** Here, cows $1$ and $2$ can be paired because their distance is $2 \leq K = 2$, and cows $4$ and $5$ can be paired because their distance is $2 \leq K = 2$. This pairing is maximal because only cow $3$ remains. The total weight of unpaired cows is $2$. **Sample Explanation 3** The answer for this example is $693+992+785=2470$. **Constraints** - Test cases 4–8 satisfy $T=1$. - Test cases 9–14 satisfy $T=2$ and $N\le 5000$. - Test cases 15–20 satisfy $T=2$. Translated by ChatGPT 5