There are a total of n (1 ≤ n ≤ 105) cows on the number line. The location of the i-th cow is given by xi, and the weight of the i-th cow is given by yi.

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, |xa − xb| ≤ 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 ≤ 109).

In each of the following n lines, the i-th contains xi (0 ≤ xi ≤ 109) and yi (1 ≤ yi ≤ 104). It is guaranteed that 0 ≤ x1 < x2 < ... < xn ≤ 109.

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.