Paired Up (Gold)#11225
There are a total of (1 \le n \le 10^5) cows on the number line. 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 two distinct cows and whose locations are within of each other; that is, |x_a - x_b| \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 , and (1 \le k \le 10^9).
In each of the following lines, the -th contains x_i (0 \le x_i \le 10^9) and y_i (1 \le y_i \le 10^4). It is guaranteed that 0 \le x_1 < x_2 < \ldots < x_n \le 10^9.
Print out the minimum or maximum possible sum of weights of the unpaired cows.
Example 1
Example 2
Example 3
Example 1
In this example, cows and can pair up because they are at distance , which is at most k = 2. This pairing is maximal, because cows and are at distance , cows and are at distance , and cows and are at distance , all of which are more than k = 2. The sum of weights of unpaired cows is 2 + 2 + 2 = 6.
Example 2
Here, cows and can pair up because they are at distance 2 \le k = 2, and cows and can pair up because they are at distance 2 \le k = 2. This pairing is maximal because only cow remains. The weight of the only unpaired cow here is simply .
Example 3
The answer for this example is 693 + 992 + 785 = 2470.