Byteland, Berland and Disputed Cities

Byteland and Berland의 도시들은 Ox축 위에 있다. 또한 이 축 위에는 양국이 각각 자국에 속한다고 여기는 분쟁 도시들도 있다. 따라서 Ox 직선 위에는 세 가지 유형의 도시가 있다:

• Byteland의 도시,
• Berland의 도시,
• 분쟁 도시.

최근 차세대 컴퓨터 네트워크 프로젝트인 BNET가 시작되었다. 이제 양국의 과제는 각 국가의 네트워크가 연결되도록 도시들을 연결하는 것이다.

양국은 다음과 같은 방식으로 도시 쌍들을 BNET 케이블로 연결하기로 합의했다:

• Byteland의 도시와 분쟁 도시만을 보면, 그렇게 이루어진 도시 집합에서는 임의의 도시에서 다른 임의의 도시로 하나 이상의 케이블을 통해 이동할 수 있어야 한다,
• Berland의 도시와 분쟁 도시만을 보면, 그렇게 이루어진 도시 집합에서는 임의의 도시에서 다른 임의의 도시로 하나 이상의 케이블을 통해 이동할 수 있어야 한다.

따라서 두 조건을 동시에 만족하도록 케이블로 연결할 도시 쌍의 집합을 선택해야 한다. 케이블은 bi-방향 데이터 전송을 허용한다. 각 케이블은 서로 다른 정확히 두 도시를 연결한다.

한 도시에서 다른 도시로 케이블을 설치하는 비용은 두 도시 사이의 거리와 같다. 두 도시 부분집합(Byteland의 도시와 분쟁 도시, Berland의 도시와 분쟁 도시)이 연결되도록 케이블 집합을 설치하는 데 필요한 최소 총비용을 구한다.

각 도시는 Ox 직선 위의 한 점이다. a, b, c가 각각 도시 a, b, c의 좌표일 때, 도시 a와 b를 케이블로 연결하면서 도시 c (a < c < b)가 이 케이블에 연결되지 않도록 하는 것이 기술적으로 가능하다.

첫 번째 줄에 도시의 수를 나타내는 하나의 정수 n (2 ≤ n ≤ 2 ⋅ $10^{5}$)이 주어진다.

이어지는 n개의 줄에는 도시의 좌표와 유형을 나타내는 정수 $x_i$와 문자 $c_i$ (-$10^{9}$ ≤ $x_i$ ≤ $10^{9}$)가 주어진다. 도시가 Byteland에 속하면 $c_i$는 'B'와 같다. 도시가 Berland에 속하면 $c_i$는 «R»과 같다. 도시가 분쟁 도시이면 $c_i$는 'P'와 같다.

모든 도시의 좌표는 서로 다르다. 도시들은 좌표가 증가하는 순서로 주어짐이 보장된다.

모든 Berland 도시 ($c_i$='R')를 삭제했을 때, 남은 임의의 도시에서 다른 임의의 남은 도시까지 케이블만을 따라 이동하는 경로를 찾을 수 있게 하는 케이블 집합의 최소 총길이를 출력한다. 마찬가지로 모든 Byteland 도시 ($c_i$='B')를 삭제했을 때도, 남은 임의의 도시에서 다른 임의의 남은 도시까지 케이블만을 따라 이동하는 경로를 찾을 수 있어야 한다.

첫 번째 예제에서는 첫 번째 도시와 두 번째 도시를, 두 번째 도시와 세 번째 도시를, 세 번째 도시와 네 번째 도시를 연결해야 한다. 케이블의 총길이는 5 + 3 + 4 = 12가 된다.

두 번째 예제에는 분쟁 도시가 없으므로, Byteland에서 서로 이웃한 모든 도시와 Berland에서 서로 이웃한 모든 도시를 연결해야 한다. Berland 도시들의 좌표는 10, 21, 32이므로, 이들을 연결하려면 길이가 11과 11인 두 개의 케이블이 필요하다. Byteland 도시들의 좌표는 14와 16이므로, 이들을 연결하려면 길이가 2인 하나의 케이블이 필요하다. 따라서 모든 케이블의 총길이는 11 + 11 + 2 = 24이다.