Problem Description

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.

Input Format

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 Format

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

2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

16

1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

6

2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540

1893

Hint

[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