Paired Up (Platinum)
There are a total of n 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], and the weight of the i-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 h and a Guernsey g whose locations are within k of each other; 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.
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.
Input
The first line contains t, n (1 ≤ n ≤ 5000) and k (1 ≤ k ≤ 10^9).
Following this are *n lines, the i-th of which contains bi, x[i] (0 ≤ x[i] ≤ 10^9), y[i] (1 ≤ y[i] ≤ 10^5). It is guaranteed that 0 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9.
Output
Print the minimum or maximum possible sum of weights of the unpaired cows.
Example 1
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.
Example 2
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.
Example 3
The answer to this example is 18 + 465 + 870 + 540 = 1893.