Byteland 和 Berland 城市位于轴 $$$Ox$$$ 上。另外,这条轴线上还存在有争议的城市,这些城市在他们看来属于各个国家。因此,$$$Ox$$$ 线上有三种类型的城市:
- Byteland 的城市,
- Berland 的城市,
- 有争议的城市。
最近,新一代计算机网络BNET项目已经启动。现在两国的任务就是把城市连接起来,让这个国家的网络连接起来。
各国同意使用 BNET 电缆连接城市对,方式如下:
- 如果您查看 Byteland 的唯一城市和有争议的城市,那么在生成的一组城市中,任何城市都应该可以通过一根或多根电缆从任何其他城市到达,
- 如果您查看 Berland 的唯一城市和有争议的城市,那么在生成的一组城市中,任何城市都应该可以通过一根或多根电缆从任何其他城市到达。
因此,需要选择一组城市对来通过电缆连接,使得这两个条件同时满足。电缆允许双向数据传输。每条电缆恰好连接两个不同的城市。
从一个城市到另一个城市铺设电缆的成本等于它们之间的距离。求铺设一组电缆以连接两个城市子集(Byteland 和有争议的城市、Berland 和有争议的城市)的最低总成本。
每个城市都是 $$$Ox$$$ 线上的一个点。从技术上讲,可以用电缆连接城市 $$$a$$$ 和 $$$b$$$,以便城市 $$$c$$$ ($$$a < c < b$$$) 不连接到该电缆,其中 $$$a$$$、$$$b$$$ 和 $$$c$$$ 同时是城市 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的坐标。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — 城市数量。
以下 $$$n$$$ 行包含整数 $$$x_i$$$ 和字母 $$$c_i$$$ ($$$-10^{9} \le x_i \le 10^{9}$$$) — 城市的坐标及其类型。如果该城市属于 Byteland,则 $$$c_i$$$ 等于“B”。如果该城市属于 Berland,则 $$$c_i$$$ 等于 «R»。如果城市有争议,$$$c_i$$$ 等于“P”。
所有城市都有不同的坐标。确保城市按照坐标升序排列。
输出
打印这样一组电缆的最小总长度,如果我们删除所有 Berland 城市 ($$$c_i$$$='R'),则可以找到从任何剩余城市到任何其他剩余城市的方法,仅通过电缆移动。同样,如果我们删除所有 Byteland 城市 ($$$c_i$$$='B'),则可以找到从任何剩余城市到任何其他剩余城市的方法,仅通过电缆移动。
示例
输入 #1
4 -5 R 0 P 3 P 7 B
输出 #1
12
输入 #2
5 10 R 14 B 16 B 21 R 32 R
输出 #2
24
注意
在第一个示例中,您应该将第一个城市与第二个城市连接,第二个城市与第三个城市连接,第三个城市与第四个城市连接。电缆的总长度为 $$$5 + 3 + 4 = 12$$$。
在第二个示例中,没有争议城市,因此您需要连接 Byteland 的所有邻近城市和 Berland 的所有邻近城市。 Berland 的城市坐标为 $$$10, 21, 32$$$,因此要连接它们,您需要两根长度为 $$$11$$$ 和 $$$11$$$ 的电缆。 Byteland 的城市坐标为 $$$14$$$ 和 $$$16$$$,因此要连接它们,您需要一根长度为 $$$2$$$ 的电缆。因此,所有电缆的总长度为 $$$11 + 11 + 2 = 24$$$。