Problem 1. Paired Up

USACO 2021 December Contest, Gold

数轴上总计有 $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$。

输出格式（输出至终端 / 标准输出）：

输出未配对的奶牛的最小或最大重量和。

输入样例：

2 5 2
1 2
3 2
4 2
5 1
7 2

输出样例：

6

在这个例子中，奶牛 $2$ 和 $4$ 可以配对，因为她们的距离为 $2$，不超过 $K = 2$。这个配对方案是极大的，因为奶牛 $1$ 和 $3$ 的距离为 $3$，奶牛 $3$ 和 $5$ 的距离为 $3$，奶牛 $1$ 和奶牛 $5$ 的距离为 $6$，均大于 $K = 2$。未配对的奶牛的重量和为 $2 + 2 + 2 = 6$。

输入样例：

1 5 2
1 2
3 2
4 2
5 1
7 2

输出样例：

2

在这里，奶牛 $1$ 和 $2$ 可以配对，因为她们的距离为 $2 \leq K = 2$，同时奶牛 $4$ 和 $5$ 可以配对，因为她们的距离为 $2 \leq K = 2$。这个配对方案是极大的，因为只剩下了奶牛 $3$。未配对的奶牛的重量和即为 $2$。

输入样例：

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

输出样例：

2470

这个例子的答案为 $693+992+785=2470$。

测试点性质： 测试点 4-8 满足 $T=1$。测试点 9-14 满足 $T=2$ 且 $N\le 5000$。测试点 15-20 满足 $T=2$。

供题：Benjamin Qi