数轴上总计有 N（1≤N≤5000）头奶牛，每一头奶牛都是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一。第 i 头奶牛的品种为 bi∈{H,G}，第 i 头奶牛的位置为 xi（0≤xi≤10^9），而第 i 头奶牛的重量为 yi（1≤yi≤10^5）。

根据 Farmer John 的信号，某些奶牛会组成对，使得 每一对包含位置相差不超过 K 的一头荷斯坦牛 h 和一头更赛牛 g（1≤K≤10^9）；也就是说，|xh−xg|≤K。 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。 配对是极大的；也就是说，没有两头未配对的奶牛可以组成对。 你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，

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

输入的第一行包含 T，N 和 K。 以下 N 行，第 i 行包含 bi,xi,yi。输入保证 0≤x1<x2<<xN≤10^9。

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

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

样例2解释： 奶牛 1 和 2 可以配对，因为她们的距离为 2≤K=4，同时奶牛 3 和 5 可以配对，因为她们的距离为 4≤K=4。这个配对方案是极大的，因为只剩下了奶牛 4。未配对的奶牛的重量和即为唯一未配对的奶牛的重量，即为 6。

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

数据规模： 测试点 4-7 满足 T=1。 测试点 8-14 满足 T=2 且 N≤300。 测试点 15-22 满足 T=2。