P7987 [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$，计算未配对的奶牛的最大重量和。

无

无

【样例解释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$。