题目描述

数轴上总计有 \(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\)。