本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

数轴上共有 $N$（$1\le N\le 10^5$）头奶牛。第 $i$ 头奶牛的位置为 $x_i$（$0 \leq x_i \leq 10^9$），体重为 $y_i$（$1 \leq y_i \leq 10^4$）。 在 Farmer John 的信号下，一些奶牛会两两配对，满足： 每一对由两头不同的奶牛 $a$ 和 $b$ 组成，且它们的位置相距不超过 $K$（$1\le K\le 10^9$）；也即 $|x_a-x_b|\le K$。 每头奶牛要么属于恰好一对配对，要么不参与配对。 该配对是极大（maximal）的；也就是说，任何两头未配对的奶牛都不能再组成一对。 你需要确定未配对奶牛体重之和的可能范围。具体地： 若 $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$。

输出格式

请输出未配对奶牛体重之和的最小值或最大值（取决于 $T$）。

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 \leq K = 2$；奶牛 $4$ 和 $5$ 也可以配对，因为它们的距离为 $2 \leq K = 2$。该配对是极大的，因为只剩下奶牛 $3$ 未配对。这里唯一未配对奶牛的体重就是 $2$。

该样例的答案为 $693+992+785=2470$。

评分（SCORING）： 测试点 4-8 满足 $T=1$。 测试点 9-14 满足 $T=2$ 且 $N\le 5000$。 测试点 15-20 满足 $T=2$。 题目来源致谢：Benjamin Qi

来源

USACO|2021|Gold