← 返回题目列表

Codeforces · 908/F

F. 新年和彩虹路

中文机器翻译题面 查看原题

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。