Cow Pairing Range

Farmer John has placed (N) cows on a number line. The (i)th cow is at position (x_i) and has weight (y_i). A pair of distinct cows (a) and (b) can be formed if and only if their positions differ by at most (K), i.e. (|x_a - x_b| \le K). A valid pairing must satisfy the following conditions:

1. Each pair consists of two distinct cows with (|x_a-x_b|\le K).
2. Every cow is either paired (appearing in exactly one pair) or left unpaired.
3. The pairing is maximal: there do not exist two unpaired cows (i) and (j) with (|x_i-x_j|\le K) (since such a pair could be added).

Depending on the value of (T), we wish to compute a different extreme of the possible sum of weights of unpaired cows. Specifically:

• If (T = 1), compute the minimum possible sum of weights of unpaired cows among all valid maximal pairings.
• If (T = 2), compute the maximum possible sum of weights of unpaired cows among all valid maximal pairings.

It can be shown that any pairing meeting the conditions can be constructed by pairing cows only when they are "forced" by the maximality requirement. In other words, if two cows that are consecutive (in sorted order by (x)) satisfy (x_{i+1}-x_i\le K), then leaving both unpaired would violate maximality – they must be paired in at least one valid configuration. Exploiting this idea, one may obtain two extreme strategies by processing the cows in sorted order:

• A left-to-right greedy pairing forms pairs whenever possible; this yields the minimum unpaired weight sum.
• A right-to‐left greedy pairing (pairing whenever possible from the right end) yields the maximum unpaired weight sum.

Your task is to implement these strategies.

All formulas are in (\LaTeX) format. For example, the pairing condition is written as (|x_a-x_b| \le K).

inputFormat

The first line contains three integers (T), (N), and (K) ( (1 \le T \le 2,\ 1 \le N \le 10^5,\ 1 \le K \le 10^9)). Each of the next (N) lines contains two integers (x_i) and (y_i) ( (0 \le x_i \le 10^9,\ 1 \le y_i \le 10^4)) describing the position and weight of a cow.

Note: The cows may be given in arbitrary order.

outputFormat

Output a single integer – the extreme (minimum if (T=1) or maximum if (T=2)) possible sum of weights of unpaired cows in a valid maximal pairing.

sample

1 3 10
0 5
1 1
100 4

4