{"raw_statement":[{"iden":"statement","content":"The cities of Byteland and Berland are located on the axis $Ox$. In addition, on this axis there are also disputed cities, which belong to each of the countries in their opinion. Thus, on the line $Ox$ there are three types of cities:\n\n*   the cities of Byteland,\n*   the cities of Berland,\n*   disputed cities.\n\nRecently, the project BNET has been launched — a computer network of a new generation. Now the task of the both countries is to connect the cities so that the network of this country is _connected_.\n\nThe countries agreed to connect _the pairs_ of cities with BNET cables in such a way that:\n\n*   If you look at the _only_ cities of Byteland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables,\n*   If you look at the _only_ cities of Berland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables.\n\nThus, it is necessary to choose a set of pairs of cities to connect by cables in such a way that both conditions are satisfied simultaneously. Cables allow bi-directional data transfer. Each cable connects exactly two distinct cities.\n\nThe cost of laying a cable from one city to another is equal to the distance between them. Find the minimum total cost of laying a set of cables so that two subsets of cities (Byteland and disputed cities, Berland and disputed cities) are connected.\n\nEach city is a point on the line $Ox$. It is technically possible to connect the cities $a$ and $b$ with a cable so that the city $c$ ($a &lt; c &lt; b$) is not connected to this cable, where $a$, $b$ and $c$ are simultaneously coordinates of the cities $a$, $b$ and $c$."},{"iden":"input","content":"The first line contains a single integer $n$ ($2 \\le n \\le 2 \\cdot 10^{5}$) — the number of cities.\n\nThe following $n$ lines contains an integer $x_i$ and the letter $c_i$ ($-10^{9} \\le x_i \\le 10^{9}$) — the coordinate of the city and its type. If the city belongs to Byteland, $c_i$ equals to '_B_'. If the city belongs to Berland, $c_i$ equals to «_R_». If the city is disputed, $c_i$ equals to '_P_'.\n\nAll cities have distinct coordinates. Guaranteed, that the cities are given in the increasing order of their coordinates."},{"iden":"output","content":"Print the minimal total length of such set of cables, that if we delete all Berland cities ($c_i$\\='_R_'), it will be possible to find a way from any remaining city to any other remaining city, moving only by cables. Similarly, if we delete all Byteland cities ($c_i$\\='_B_'), it will be possible to find a way from any remaining city to any other remaining city, moving only by cables."},{"iden":"examples","content":"Input\n\n4\n-5 R\n0 P\n3 P\n7 B\n\nOutput\n\n12\n\nInput\n\n5\n10 R\n14 B\n16 B\n21 R\n32 R\n\nOutput\n\n24"},{"iden":"note","content":"In the first example, you should connect the first city with the second, the second with the third, and the third with the fourth. The total length of the cables will be $5 + 3 + 4 = 12$.\n\nIn the second example there are no disputed cities, so you need to connect all the neighboring cities of Byteland and all the neighboring cities of Berland. The cities of Berland have coordinates $10, 21, 32$, so to connect them you need two cables of length $11$ and $11$. The cities of Byteland have coordinates $14$ and $16$, so to connect them you need one cable of length $2$. Thus, the total length of all cables is $11 + 11 + 2 = 24$."}],"translated_statement":[{"iden":"statement","content":"比特兰和贝兰的城市位于坐标轴 $O x$ 上。此外，该轴上还存在一些争议城市，这两个国家都声称对其拥有主权。因此，在直线 $O x$ 上共有三种类型的城市：\n\n最近，启动了名为 BNET 的项目——新一代计算机网络。现在，两国的任务是连接城市，使得各自国家的网络是 _连通的_。\n\n两国达成协议，通过 BNET 电缆连接 _成对_ 的城市，满足以下条件：\n\n因此，需要选择一组城市对，通过电缆连接，使得两个条件同时满足。电缆支持双向数据传输，每条电缆恰好连接两个不同的城市。\n\n铺设一条从一个城市到另一个城市的电缆的成本等于它们之间的距离。请找出铺设一组电缆的最小总成本，使得两个城市子集（比特兰城市和争议城市、贝兰城市和争议城市）分别连通。\n\n每个城市是 $O x$ 轴上的一个点。技术上允许连接城市 $a$ 和 $b$（其中 $a < c < b$），即使城市 $c$ 并未直接连接到该电缆，其中 $a$、$b$ 和 $c$ 分别是城市 $a$、$b$ 和 $c$ 的坐标。\n\n第一行包含一个整数 $n$（$2 lt.eq n lt.eq 2 dot.op 10^5$）——城市的数量。\n\n接下来的 $n$ 行，每行包含一个整数 $x_i$ 和一个字母 $c_i$（$-10^9 lt.eq x_i lt.eq 10^9$）——城市的坐标及其类型。如果城市属于比特兰，则 $c_i$ 为 '_B_'；如果属于贝兰，则 $c_i$ 为 «_R_'；如果为争议城市，则 $c_i$ 为 '_P_'。\n\n所有城市的坐标互不相同。保证城市按坐标递增顺序给出。\n\n请输出一组电缆的最小总长度，使得：若删除所有贝兰城市（$c_i$='_R_'），剩余城市之间仍可通过电缆相互连通；同样，若删除所有比特兰城市（$c_i$='_B_'），剩余城市之间仍可通过电缆相互连通。\n\n在第一个示例中，应连接第一座城市与第二座、第二座与第三座、第三座与第四座。电缆总长度为 $5 + 3 + 4 = 12$。\n\n在第二个示例中，没有争议城市，因此需要连接所有相邻的比特兰城市和所有相邻的贝兰城市。贝兰城市的坐标为 $10, 21, 32$，连接它们需要两条长度为 $11$ 和 $11$ 的电缆；比特兰城市的坐标为 $14$ 和 $16$，连接它们需要一条长度为 $2$ 的电缆。因此，所有电缆的总长度为 $11 + 11 + 2 = 24$。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$（$2 lt.eq n lt.eq 2 dot.op 10^5$）——城市的数量。接下来的 $n$ 行，每行包含一个整数 $x_i$ 和一个字母 $c_i$（$-10^9 lt.eq x_i lt.eq 10^9$）——城市的坐标及其类型。如果城市属于比特兰，则 $c_i$ 为 '_B_'；如果属于贝兰，则 $c_i$ 为 «_R_'；如果为争议城市，则 $c_i$ 为 '_P_'。所有城市的坐标互不相同。保证城市按坐标递增顺序给出。"},{"iden":"output","content":"请输出一组电缆的最小总长度，使得：若删除所有贝兰城市（$c_i$='_R_'），剩余城市之间仍可通过电缆相互连通；同样，若删除所有比特兰城市（$c_i$='_B_'），剩余城市之间仍可通过电缆相互连通。"},{"iden":"examples","content":"输入4-5 R0 P3 P7 B输出12输入510 R14 B16 B21 R32 R输出24"},{"iden":"note","content":"在第一个示例中，应连接第一座城市与第二座、第二座与第三座、第三座与第四座。电缆总长度为 $5 + 3 + 4 = 12$。在第二个示例中，没有争议城市，因此需要连接所有相邻的比特兰城市和所有相邻的贝兰城市。贝兰城市的坐标为 $10, 21, 32$，连接它们需要两条长度为 $11$ 和 $11$ 的电缆；比特兰城市的坐标为 $14$ 和 $16$，连接它们需要一条长度为 $2$ 的电缆。因此，所有电缆的总长度为 $11 + 11 + 2 = 24$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of cities.  \nLet $ C = \\{(x_i, t_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of cities, where:  \n- $ x_i \\in \\mathbb{R} $ is the coordinate of city $ i $, with $ x_1 < x_2 < \\dots < x_n $,  \n- $ t_i \\in \\{B, R, P\\} $ is the type of city $ i $: Byteland ($B$), Berland ($R$), or disputed ($P$).  \n\nLet $ V_B = \\{x_i \\mid t_i = B \\text{ or } t_i = P\\} $ be the set of coordinates of cities belonging to Byteland (including disputed).  \nLet $ V_R = \\{x_i \\mid t_i = R \\text{ or } t_i = P\\} $ be the set of coordinates of cities belonging to Berland (including disputed).  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 2 \\cdot 10^5 $  \n2. All $ x_i $ are distinct and given in strictly increasing order.  \n3. $ -10^9 \\leq x_i \\leq 10^9 $  \n\n**Objective**  \nFind the minimum total length of a set of cables (edges) such that:  \n- The subgraph induced on $ V_B $ is connected,  \n- The subgraph induced on $ V_R $ is connected.  \n\nEach cable connects two distinct cities $ (x_i, x_j) $ with cost $ |x_i - x_j| $, and cables may span over cities not directly connected.  \n\nThe solution is the sum of the minimum spanning tree (MST) costs for $ V_B $ and $ V_R $, computed independently.  \n\nSince all points lie on a line and are sorted, the MST of a set of collinear points is simply the union of edges between consecutive points in the set.  \n\nThus, for each set $ S \\in \\{V_B, V_R\\} $, let $ s_1 < s_2 < \\dots < s_m $ be the sorted coordinates in $ S $. Then the MST cost for $ S $ is:  \n$$\n\\sum_{j=1}^{m-1} (s_{j+1} - s_j)\n$$\n\nThe total minimal cost is:  \n$$\n\\sum_{\\substack{(x_i, x_{i+1}) \\in V_B \\\\ \\text{consecutive}}} (x_{i+1} - x_i) + \\sum_{\\substack{(x_i, x_{i+1}) \\in V_R \\\\ \\text{consecutive}}} (x_{i+1} - x_i)\n$$","simple_statement":null,"has_page_source":false}