# [USACO21DEC] Paired Up G
## 题目描述
数轴上总计有 $N$（$1\le N\le 10^5$）头奶牛。第 $i$ 头奶牛的位置为 $x_i$（$0 \leq x_i \leq 10^9$），而第 $i$ 头奶牛的重量为 $y_i$（$1 \leq y_i \leq 10^4$）。
根据 Farmer John 的信号，某些奶牛会组成对，使得
- 每一对包含位置相差不超过 $K$ 的两头不同的奶牛 $a$ 和 $b$（$1\le K\le 10^9$）；也就是说，$|x_a-x_b|\le K$。
- 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。
- **配对是极大的**；也就是说，没有两头未配对的奶牛可以组成对。
你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，
- 如果 $T=1$，计算未配对的奶牛的最小重量和。
- 如果 $T=2$，计算未配对的奶牛的最大重量和。
## 输入格式
输入的第一行包含 $T$，$N$ 和 $K$。
以下 $N$ 行，第 $i$ 行包含 $x_i$ 和 $y_i$。输入保证 $0\le x_1< x_2<\cdots<x_{N}\le 10^9$。
## 输出格式
输出未配对的奶牛的最小或最大重量和。
## 样例 #1
### 样例输入 #1
```
2 5 2
1 2
3 2
4 2
5 1
7 2
```
### 样例输出 #1
```
6
```
## 样例 #2
### 样例输入 #2
```
1 5 2
1 2
3 2
4 2
5 1
7 2
```
### 样例输出 #2
```
2
```
## 样例 #3
### 样例输入 #3
```
2 15 7
3 693
10 196
12 182
14 22
15 587
31 773
38 458
39 58
40 583
41 992
84 565
86 897
92 197
96 146
99 785
```
### 样例输出 #3
```
2470
```
## 提示
【样例解释1】
在这个例子中，奶牛 $2$ 和 $4$ 可以配对，因为她们的距离为 $2$，不超过 $K = 2$。这个配对方案是极大的，因为奶牛 $1$ 和 $3$ 的距离为 $3$，奶牛 $3$ 和 $5$ 的距离为 $3$，奶牛 $1$ 和奶牛 $5$ 的距离为 $6$，均大于 $K = 2$。未配对的奶牛的重量和为 $2 + 2 + 2 = 6$。
【样例解释2】
在这里，奶牛 $1$ 和 $2$ 可以配对，因为她们的距离为 $2 \leq K = 2$，同时奶牛 $4$ 和 $5$ 可以配对，因为她们的距离为 $2 \leq K = 2$。这个配对方案是极大的，因为只剩下了奶牛 $3$。未配对的奶牛的重量和即为 $2$。
【样例解释3】
这个例子的答案为 $693+992+785=2470$。
【数据范围】
- 测试点 4-8 满足 $T=1$。
- 测试点 9-14 满足 $T=2$ 且 $N\le 5000$。
- 测试点 15-20 满足 $T=2$。
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 xi
(0≤xi≤10
9), and the weight of the i
-th cow is given by yi
(1≤yi≤10
4).
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 (1≤K≤109); 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