题目描述

数轴上总计有 $N$（$1 \leq N \leq 5000$）头奶牛，每一头奶牛都是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一。第 $i$ 头奶牛的品种为 $b_i \in \{\texttt{H},\texttt{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 \leq K \leq 10^9$）；也就是说，$|x_h - x_g| \leq K$。
• 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。
• 配对是极大的；也就是说，没有两头未配对的奶牛可以组成对。

你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，

• 如果 $T=1$，计算未配对的奶牛的最小重量和。
• 如果 $T=2$，计算未配对的奶牛的最大重量和。

---

输入格式

输入的第一行包含 $T$，$N$ 和 $K$。
以下 $N$ 行，第 $i$ 行包含 $b_i, x_i, y_i$。输入保证 $0 \leq x_1 < x_2 < \dots < x_N \leq 10^9$。

---

输出格式

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

---

样例 1

输入

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

输出

16

解释
奶牛 2 和 3 可以配对，因为她们的距离为 $1$，不超过 $K=4$。这个配对方案是极大的，因为奶牛 1（唯一余下的更赛牛）和奶牛 4 的距离为 $5$，和奶牛 5 的距离为 $7$，均大于 $K=4$。未配对的奶牛的重量和为 $1+6+9=16$。

---

样例 2

输入

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

输出

6

解释
奶牛 1 和 2 可以配对，因为她们的距离为 $2 \leq K=4$，同时奶牛 3 和 5 可以配对，因为她们的距离为 $4 \leq K=4$。这个配对方案是极大的，因为只剩下了奶牛 4。未配对的奶牛的重量和即为唯一未配对的奶牛的重量，即为 $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

输出

1893

解释
这个例子的答案为 $18+465+870+540=1893$。

---

数据范围与提示

• 测试点 $4$-$7$ 满足 $T=1$。
• 测试点 $8$-$14$ 满足 $T=2$ 且 $N \leq 300$。
• 测试点 $15$-$22$ 满足 $T=2$。

---