4572: Paired Up

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