Roy 和 Biv 在无限数轴上有一组 n 个点。
每个点都有 3 种颜色之一:红色、绿色或蓝色。
Roy 和 Biv 希望用一些边连接所有点。可以在任意两个给定点之间绘制边。一条边的成本等于它所连接的两点之间的距离。
他们希望以这样一种方式来做到这一点,即他们都将看到所有点都是连接的(直接或间接)。
但是,有一个问题:Roy 看不到红色,Biv 看不到蓝色。
因此,他们必须以这样的方式选择边:如果所有红点被移除,则剩余的蓝色和绿色点被连接(同样,如果所有蓝色点被移除,则剩余的红色和绿色点被连接)。
帮助他们计算选择边以满足上述约束的最小成本方式。
输入
第一行将包含一个整数 n (1 ≤ n ≤ 300 000),即点数。
接下来的n行将包含两个标记pi和ci(pi是整数,1≤pi≤109,ci是大写英文字母'R','G'或'B'),表示第i个点的位置和第i个点的颜色。 “R”表示红色,“G”表示绿色,“B”表示蓝色。职位将严格按升序排列。
输出
打印单个整数,解决问题的最小成本方式。
示例
输入 #1
4 1 G 5 R 10 B 15 G
输出 #1
23
输入 #2
4 1 G 2 R 3 B 10 G
输出 #2
12
注意
在第一个示例中,最好在点 (1,2)、(1,4)、(3,4) 之间绘制边缘。它们的成本分别为 4、14、5。