Paired Up
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 bi∈{H,G}, the location of the i-th cow is given by xi (0≤xi≤109), and the weight of the i-th cow is given by yi (1≤yi≤105).
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≤109); that is, ∣xh−xg∣≤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.
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.
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.
The answer to this example is 18+465+870+540=1893.
SCORING:
- Test cases 4-7 satisfy T=1.
- Test cases 8-14 satisfy T=2 and N≤300.
- Test cases 15-22 satisfy T=2.
**Note: the memory limit for this problem is 512MB, twice the default.**
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first input line contains T, N, and K.
Following this are N lines, the i-th of which contains bi,xi,yi. It is guaranteed that 0≤x1<x2<⋯<xN≤109.
Output Format
The minimum or maximum possible sum of weights of the unpaired cows.