Paired Up (Platinum)#11229
There are a total of cows on the number line, each of which is a **Holstein** or a **Guernsey**. The breed of the -th cow is given by b_i \in \{H, G\}, the location of the -th cow is given by x_i, and the weight of the -th cow is given by y_i.
At Farmer John's signal, some of the cows will form pairs such that
- Every pair consists of a Holstein and a Guernsey whose locations are within of each other; that is, |x_h - x_g| \le 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.
It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,
- 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.
The first line contains , (1 \le n \le 5000) and (1 \le k \le 10^9).
Following this are lines, the -th of which contains b_i, x_i (0 \le x_i \le 10^9), y_i (1 \le y_i \le 10^5). It is guaranteed that 0 \le x_1 < x_2 < \ldots < x_n \le 10^9.
Print the minimum or maximum possible sum of weights of the unpaired cows.
Example 1
Example 2
Example 3
**Example 1:** Cows and can pair up because they are at distance , which is at most k = 4. This pairing is maximal, because cow , the only remaining Guernsey, is at distance from cow and distance from cow , which are more than k = 4. The sum of weights of unpaired cows is 1 + 6 + 9 = 16.
**Example 2:** Cows and can pair up because they are at distance 2 \le k = 4, and cows and can pair up because they are at distance 4 \le k = 4. This pairing is maximal because only cow remains. The sum of weights of unpaired cows is the weight of the only unpaired cow, which is simply .
**Example 3:** The answer to this example is 18 + 465 + 870 + 540 = 1893.