P7985 [USACO21DEC] Paired Up P

There are a total of $N$ cows on a number line ($1 \le N \le 5000$). Each cow is either a Holstein or a Guernsey. For cow $i$, its breed is $b_i \in \{H,G\}$, its position is $x_i$ ($0 \le x_i \le 10^9$), and its weight is $y_i$ ($1 \le y_i \le 10^5$). Following Farmer John’s signal, some cows will form pairs such that: - Each pair consists of one Holstein cow $h$ and one Guernsey cow $g$ whose positions differ by at most $K$ ($1 \le K \le 10^9$); that is, $|x_h - x_g| \le K$. - Each cow is either included in exactly one pair or belongs to no 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 next $N$ lines describe the cows. Line $i$ contains $b_i, x_i, y_i$. The input guarantees that $0 \le x_1 < x_2 < \cdots < x_N \le 10^9$.

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

[Sample Explanation 1] Cows $2$ and $3$ can be paired because their distance is $1$, which does not exceed $K = 4$. This pairing is maximal because cow $1$, the only remaining Guernsey, is at distance $5$ from cow $4$ and at distance $7$ from cow $5$, both greater than $K = 4$. The total weight of unpaired cows is $1 + 6 + 9 = 16$. [Sample Explanation 2] Cows $1$ and $2$ can be paired because their distance is $2 \le K = 4$, and cows $3$ and $5$ can be paired because their distance is $4 \le K = 4$. This pairing is maximal because only cow $4$ remains. The total weight of unpaired cows is the weight of the only unpaired cow, which is $6$. [Sample Explanation 3] The answer for this example is $18 + 465 + 870 + 540 = 1893$. [Constraints] - Test cases 4-7 satisfy $T = 1$. - Test cases 8-14 satisfy $T = 2$ and $N \le 300$. - Test cases 15-22 satisfy $T = 2$. **Note: The memory limit for this problem is $\text{512MB}$, which is twice the usual limit.** Translated by ChatGPT 5