8137: USACO 2021 December Contest, Platinum Problem 2. Paired Up
[Creator : ]
Description
There are a total of N (1≤N≤5000) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the i-th cow is given by $b_i∈{H,G}$, the location of the i-th cow is given by $x_i\ (0≤x_i≤10^9)$, and the weight of the i-th cow is given by $y_i\ (1≤y_i≤10^5)$.
At Farmer John's signal, some of the cows will form pairs such that
- Every pair consists of a Holstein hℎ and a Guernsey g whose locations are within K of each other $(1≤K≤10^9)$; that is, $|x_h−x_g|≤K$.
- Every cow is either part of a single pair or not part of a pair.
- The pairing is maximal; that is, no two unpaired cows can form a pair.
- If T=1, compute the minimum possible sum of weights of the unpaired cows.
- If T=2, compute the maximum possible sum of weights of the unpaired cows.
Input
The first input line contains T, N, and K.
Following this are N lines, the i-th of which contains $b_i,x_i,y_i$.
It is guaranteed that $0≤x_1<x_2<⋯<x_N≤10^9$.
It is guaranteed that $0≤x_1<x_2<⋯<x_N≤10^9$.
Output
The minimum or maximum possible sum of weights of the unpaired cows.
Sample 1 Input
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
Sample 1 Output
16
Cows 2 and 3 can pair up because they are at distance 1, which is at most K=4. This pairing is maximal, because cow 1, the only remaining Guernsey, is at distance 5 from cow 4 and distance 7 from cow 5, which are more than K=4. The sum of weights of unpaired cows is 1+6+9=16.
Sample 2 Input
1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
Sample 2 Output
6
Cows 1 and 2 can pair up because they are at distance 2≤K=4, and cows 3 and 5 can pair up because they are at distance 4≤K=4. This pairing is maximal because only cow 4 remains. The sum of weights of unpaired cows is the weight of the only unpaired cow, which is simply 6.
Sample 3 Input
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 3 Output
1893
The answer to this example is 18+465+870+540=1893.
HINT
相同题目：USACO Platinum。