[USACO21DEC] Paired Up P

题目描述

数轴上总计有 $N$($1\le N\le 5000$)头奶牛,每一头奶牛都是荷斯坦牛(Holstein)或更赛牛(Guernsey)之一。第 $i$ 头奶牛的品种为 $b_i\in \{H,G\}$,第 $i$ 头奶牛的位置为 $x_i$($0 \leq x_i \leq 10^9$),而第 $i$ 头奶牛的重量为 $y_i$($1 \leq y_i \leq 10^5$)。 根据 Farmer John 的信号,某些奶牛会组成对,使得 - 每一对包含位置相差不超过 $K$ 的一头荷斯坦牛 $h$ 和一头更赛牛 $g$($1\le K\le 10^9$);也就是说,$|x_h-x_g|\le K$。 - 每一头奶牛要么包含在恰好一对中,要么不属于任何一对。 - 配对是**极大的**;也就是说,没有两头未配对的奶牛可以组成对。 你需要求出未配对的奶牛的重量之和的可能的范围。具体地说, - 如果 $T=1$,计算未配对的奶牛的最小重量和。 - 如果 $T=2$,计算未配对的奶牛的最大重量和。

输入输出格式

输入格式


输入的第一行包含 $T$,$N$ 和 $K$。 以下 $N$ 行,第 $i$ 行包含 $b_i,x_i,y_i$。输入保证 $0\le x_1<x_2<\cdots<x_{N}\le 10^9$。

输出格式


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

输入输出样例

输入样例 #1

2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

输出样例 #1

16

输入样例 #2

1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

输出样例 #2

6

输入样例 #3

2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540

输出样例 #3

1893

说明

【样例解释1】 奶牛 $2$ 和 $3$ 可以配对,因为她们的距离为 $1$,不超过 $K = 4$。这个配对方案是极大的,因为奶牛 $1$,唯一余下的更赛牛,和奶牛 $4$ 的距离为 $5$,和奶牛 $5$ 的距离为 $7$,均大于 $K = 4$。未配对的奶牛的重量和为 $1 + 6 + 9 = 16$。 【样例解释2】 奶牛 $1$ 和 $2$ 可以配对,因为她们的距离为 $2 \leq K = 4$,同时奶牛 $3$ 和 $5$ 可以配对,因为她们的距离为 $4 \leq K = 4$。这个配对方案是极大的,因为只剩下了奶牛 $4$。未配对的奶牛的重量和即为唯一未配对的奶牛的重量,即为 $6$。 【样例解释3】 这个例子的答案为 $18+465+870+540=1893$。 【数据范围】 - 测试点 4-7 满足 $T=1$; - 测试点 8-14 满足 $T=2$ 且 $N\le 300$; - 测试点 15-22 满足 $T=2$。 **注意:本题的内存限制为 $\text{512MB}$,是通常限制的两倍。**