题目描述

数轴上总计有 $N$（$1\le N\le 10^5$）头奶牛。第 $i$ 头奶牛的位置为 $x_i$（$0\le x_i\le 10^9$），而第 $i$ 头奶牛的重量为 $y_i$（$1\le y_i\le 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<\dots<x_N\le 10^9$。

输出格式

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

样例

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

6

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

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

样例解释

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

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

对于第三个样例，答案为 $693+992+785=2470$。

测试点性质

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

供题：Benjamin Qi