在数轴上有 $N$ ($1 \le N \le 5000$) 头奶牛，每头奶牛要么是荷斯坦牛（Holstein），要么是更赛牛（Guernsey）。第 $i$ 头奶牛的品种由 $b_i \in \{H, G\}$ 给出，位置由 $x_i$ ($0 \le x_i \le 10^9$) 给出，体重由 $y_i$ ($1 \le y_i \le 10^5$) 给出。

在农夫约翰发出信号后，一些奶牛将组成配对，满足：

• 每个配对由一头荷斯坦牛 $h$ 和一头更赛牛 $g$ 组成，且它们的位置距离不超过 $K$ ($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 < \dots < 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

说明 1

奶牛 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

样例输出 2

6

说明 2

奶牛 1 和 2 可以配对，因为它们的距离为 $2 \le K=4$；奶牛 3 和 5 可以配对，因为它们的距离为 $4 \le 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

样例输出 3

1893

说明 3

该样例的答案为 $18+465+870+540=1893$。

子任务

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

注意：本题内存限制为 512MB，是默认限制的两倍。

题目来源：Benjamin Qi