题目描述

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