색깔이 있는 하노이 탑

이 문제는 잘 알려진 하노이 탑 문제의 변형이다.

원래의 하노이 탑 문제에는 막대기-1, 막대기-2, 막대기-3 세 개의 막대기가 있다. 막대기-1에는 크기가 서로 다른 $n$개의 디스크가 내림차순으로 쌓여 있다. 즉, 가장 작은 디스크가 가장 위에, 가장 큰 디스크가 가장 아래에 놓여 있다. 목표는 막대기-1에 있는 모든 디스크를 막대기-3으로 옮기는 것이다. 옮기는 과정에서 한 번에 하나의 디스크만 옮길 수 있으며, 어떤 경우에도 큰 디스크를 작은 디스크 위에 놓아서는 안 된다.

원래의 문제는 다음과 같이 변형된다.

1. 같은 크기의 디스크가 허용된다. 따라서 디스크를 옮기는 과정에서 어떤 디스크는 크기가 같거나 더 큰 디스크 위에 놓을 수 있다.
2. 각 디스크는 빨간색(R), 녹색(G), 파란색(B) 중 하나로 칠해져 있다. 같은 크기의 디스크는 항상 같은 색을 가진다.
3. 같은 크기의 디스크가 둘 이상이면, 디스크의 색에 따라 모든 이동이 끝난 뒤 이들의 상대적인 순서가 정해진다. 빨간색이면 모든 디스크를 옮긴 뒤 같은 크기 디스크의 상대적인 순서가 처음과 반대여야 한다. 파란색이면 모든 디스크를 옮긴 뒤 상대적인 순서가 처음과 같아야 한다. 녹색이면 이동 후의 상대적인 순서는 상관없다. 다만 디스크를 옮기는 중간 과정에서는 이 순서 조건을 만족할 필요가 없다.
4. 디스크 이동의 총 횟수를 최소화해야 한다.

그림 C.1은 모든 디스크를 옮긴 후, 같은 크기 디스크의 색에 따른 상대적인 순서 조건을 만족하는 예를 보여준다.

그림 C.1

입력은 표준 입력을 사용한다. 첫 번째 줄에 정수 $m$ ($1 \le m \le 25$)이 주어진다. $m$은 가장 큰 디스크의 지름이다. 이어지는 $m$줄에서 $i$번째 줄 ($1 \le i \le m$)에는 영어 대문자 하나와 정수 $k$ ($\ge 1$)가 주어진다. 대문자는 지름이 $i$인 디스크의 색을, $k$는 같은 크기 디스크의 개수를 나타낸다. R은 빨간색, G는 녹색, B는 파란색이다. 1부터 $m$까지 각 지름마다 그 지름을 가진 디스크가 적어도 하나 존재한다.

쌓여 있는 디스크의 총 개수는 50을 넘지 않는다.

출력은 표준 출력을 사용한다. 한 줄에 색에 따른 상대적인 순서 조건을 만족하면서 막대기-1에 있는 모든 디스크를 막대기-3으로 옮기는 데 필요한 최소 이동 횟수를 출력한다.