Problem Description

On a number line, there are a total of $N$ ($1 \le N \le 5000$) cows, each of which is either a Holstein or a Guernsey. The breed of the $i$-th cow is $b_i \in \{H, G\}$, the position of the $i$-th cow is $x_i$ ($0 \le x_i \le 10^9$), and the weight of the $i$-th cow is $y_i$ ($1 \le y_i \le 10^5$).

According to Farmer John's signal, certain cows will pair up such that:

• Each pair consists of a Holstein cow $h$ and a Guernsey cow $g$ with a position difference not exceeding $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 is not included in any pair.
• The pairing is maximal; that is, no two unpaired cows can form a pair.

You need to determine the possible range of the sum of the weights of the unpaired cows. Specifically:

• If $T = 1$, calculate the minimum sum of weights of the unpaired cows.
• If $T = 2$, calculate the maximum sum of weights of the unpaired cows.

Input Format

The first line of input contains $T$, $N$, and $K$.

The following $N$ lines, the $i$-th line 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 sum of weights of the unpaired cows.

Sample Input and Output

Sample Input #1

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

Sample Output #1

16

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

1893

Notes

Sample Explanation 1:

Cows $2$ and $3$ can pair up because their distance is $1$, which does not exceed $K = 4$. This pairing scheme is maximal because cow $1$, the only remaining Guernsey, has distances of $5$ and $7$ to cows $4$ and $5$, respectively, both greater than $K = 4$. The sum of weights of unpaired cows is $1 + 6 + 9 = 16$.

Sample Explanation 2:

Cows $1$ and $2$ can pair up because their distance is $2 \le K = 4$, and cows $3$ and $5$ can pair up because their distance is $4 \le K = 4$. This pairing scheme is maximal because only cow $4$ remains. The sum of weights 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$.

Data Range:

• 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 512MB, which is twice the usual limit.

见题面 Input 部分

见题面 Output 部分