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